We 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.
Dynamically switching vertices in planar graphs / Frigioni, D.; Italiano, Giuseppe Francesco. - In: ALGORITHMICA. - ISSN 0178-4617. - 28:(2000), pp. 76-103. [10.1007/s004530010032]
Dynamically switching vertices in planar graphs
ITALIANO G
2000
Abstract
We 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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.