1,720,970 research outputs found
An experimental study of dynamic algorithms for transitive closure
No full texthttp://www.jea.acm.org/2001/FrigioniTransitive
Dynamically switching vertices in planar graphs
No full textWe consider graphs whose vertices may be in one of two different states: either on or off . We wish to maintain dynamically such graphs under an intermixed sequence of updates and queries. An update may reverse the status of a vertex, by switching it either on or off , and may insert a new edge or delete an existing edge. A query tests whether any two given vertices are connected in the subgraph induced by the vertices that are on . We give efficient algorithms that maintain information about connectivity on planar graphs in O( log3 n) amortized time per query, insert, delete, switch-on, and switch-off operation over sequences of at least Ω(n) operations, where n is the number of vertices of the graph
Explore and repair graphs with black holes using mobile entities
Full text linkIn this paper, we study the problem of mobile entities that synchronously have to explore and repair a graph with faulty nodes, usually called black-holes, that destroy any entering entity. We consider the scenario where the destruction of an entity by means of a black-hole also affects all the entities within a fixed range r (in terms of number of edges), while the black-hole disappears. Clearly, if there are b black-holes in the graph, then k >= b entities are necessary to remove all of them from that graph. We ask for the minimum number of synchronous steps needed to make safe all the graph.
The results of this paper are both theoretical and experimental, and can be summarized as follows. From the theoretical point of view, first we show that the problem is NP-hard even for b = k = 1. Then, we provide a general lower bound holding when r >= 0 and a higher one for the case of r > 0. We then consider the case of r <= 1. We propose an optimal solution holding when k is unbounded, that is, an infinite number of robots is available. Then, we provide three different exploration strategies, named snake, scout, and parallel-scout, respectively, for the case of bounded k, that is, the number of robots is fixed a priori. The three strategies are then analyzed according to the time complexity with respect to the lower bound. From the experimental point of view, we implemented the three strategies and tested them on different scenarios with the aim of assessing their practical performance. The experiments confirm the theoretical analysis and show that parallel-scout is always by far the best exploration strategy in practic
- …
