Catálogo de publicaciones - libros

We consider the problem of maintaining a minimum spanning tree within a graph with dynamically changing edge weights. An online algorithm is confronted with an input sequence of edge weight changes and has to choose a minimum spanning tree after each such change in the graph. The task of the algorithm is to perform as few changes in its minimum spanning tree as possible.

We compare the number of changes in the minimum spanning tree produced by an online algorithm and that produced by an optimal offline algorithm. The number of changes is counted in the number of edges changed between spanning trees in consecutive rounds.

For any graph with vertices we provide a deterministic algorithm achieving a competitive ratio of . We show that this result is optimal up to a constant. Furthermore we give a lower bound for randomized algorithms of Ω(log). We show a randomized algorithm achieving a competitive ratio of for general graphs and for planar graphs.

Prior algorithms known for exactly solving improve upon the trivial upper bound only for very sparse instances. We present new algorithms for exactly solving (in fact, counting) weighted instances. One of them has a good performance if the underlying constraint graph has a small separator decomposition, another has a slightly improved worst case performance. For a 2 instance  with variables, the worst case running time is , where is the average degree in the constraint graph defined by .

We use strict -gadgets introduced by Trevisan, Sorkin, Sudan, and Williamson to get the same upper bounds for problems like 3 and . We also introduce a notion of strict (,)-gadget to provide a framework that allows composition of gadgets. This framework allows us to obtain the same upper bounds for and 2.

We consider a problem of computing the maximal value associated to the nodes of a network in the model of unknown symmetric radio network with availability of collision detection. We assume that the nodes have no initial knowledge about the network topology, number of nodes and even they have no identifiers. The network contains one distinguished node, called initiator, that starts the process of computing. We design a series of algorithms that result into an asymptotically optimal deterministic algorithm completing the task in ( + log) rounds, where is the eccentricity of the initiator and is the maximal value among the integer values associated to the nodes. Some other utilisations of the developed algorithm are presented as well.

We build on a framework for modelling and investigating component-based systems that strictly separates the description of behavior of components from the way they interact. We discuss various properties of system behavior as liveness, local progress, local and global deadlock, and robustness. We present a criterion that ensures liveness and can be tested in polynomial time.

We give constructions of small probabilistic and MO-type quantum automata that have undecidable emptiness problem for the cut-point languages.

The distributed synthesis problem [11] is known to be undecidable. Our purpose here is to study further this undecidability.

For this, we consider distributed games [8], an infinite variant of Peterson and Reif multiplayer games with partial information [10], in which Pnueli and Rosner’s distributed synthesis problem can be encoded and, when decidable [11,6,7], uniformly solved [8].

We first prove that even the simple problem of solving 2-process distributed game with reachability conditions is undecidable (-complete). This decision problem, equivalent to two process distributed synthesis with fairly restricted FO-specification was left open [8]. We prove then that the safety case is -complete. More generally, we establish a correspondence between 2-process distributed game with Mostowski’s weak parity conditions [9] and levels of the arithmetical hierarchy. finally, distributed games with general -regular infinitary conditions are shown to be highly undecidable (-complete).

Many applications in sensor networks require positional information of the sensors. Recovering node positions is closely related to graph realization problems for geometric graphs. Here, we address the case where nodes have angular information. Whereas Bruck et al. proved that the corresponding realization problem together with unit-disk-graph-constraints is -hard [2], we focus on rigid components which allow both efficient identification and fast, unique realizations. Our technique allows to identify maximum rigid components in graphs with partially known rigid components using a reduction to maximum flow problems. This approach is analyzed for the two-dimensional case, but can easily be extended to higher dimensions.

Efficient network management system is necessary in order to provide QoS sensitive multimedia services while enhancing network performance. In this paper, we propose a new online network management algorithm based on adaptive online control strategy. Simulation results indicate the superior performance of our proposed algorithm under widely varying diverse traffic loads.

We contribute to the research on stable minimum storage merging by introducing an algorithm that is particularly simply structured compared to its competitors. The presented algorithm performs comparisons and (( + )log) assignments, where and are the sizes of the input sequences with  ≤ . Hence, according to the lower bounds of merging the algorithm is asymptotically optimal regarding the number of comparisons.

As central new idea we present a principle of symmetric splitting, where the start and end point of a rotation are computed by a repeated halving of two search spaces. This principle is structurally simpler than the principle of symmetric comparisons introduced earlier by Kim and Kutzner. It can be transparently implemented by few lines of Pseudocode.

We report concrete benchmarks that prove the practical value of our algorithm.

Previous researches on multidimensional indexes typically have used synthetic data sets distributed uniformly or normally over multidimensional space for performance evaluation. These kinds of data sets hardly reflect the characteristics of multimedia database applications. In this paper, we discuss issues on generating high dimensional data and query sets for resolving the problem. We first identify the requirements of the data and query sets for fair performance evaluation of multidimensional indexes, and then propose HDDQ_Gen (High-Dimensional Data and Query Generator) that satisfies such requirements. HDDQ_Gen has the following features: (1) clustered distribution, (2) various object distribution in each cluster, (3) various cluster distribution, (4) various correlations among different dimensions, and (5) query distribution depending on data distribution. Using these features, users are able to control the distribution characteristics of data and query sets appropriate for their target applications.