Back to Search
Start Over
Optimal Decremental Connectivity in Planar Graphs.
- Source :
-
Theory of Computing Systems . Nov2017, Vol. 61 Issue 4, p1037-1053. 17p. - Publication Year :
- 2017
-
Abstract
- We show an algorithm for dynamic maintenance of connectivity information in an undirected planar graph subject to edge deletions. Our algorithm may answer connectivity queries of the form 'Are vertices u and v connected with a path?" in constant time. The queries can be intermixed with any sequence of edge deletions, and the algorithm handles all updates in a total of O( n) time. This results improves over a previously known O( n log n) time algorithm. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 14324350
- Volume :
- 61
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Theory of Computing Systems
- Publication Type :
- Academic Journal
- Accession number :
- 125616744
- Full Text :
- https://doi.org/10.1007/s00224-016-9709-x