On-line maintenance of the four-connected components of a graph
- 1 January 1991
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 74, 793-801
- https://doi.org/10.1109/sfcs.1991.185451
Abstract
Given a graph G with n vertices and m edges, a k-connectivity query for vertices v' and v" of G asks whether there exist k disjoint paths between v' and v". The authors consider the problem of performing k-connectivity queries for kKeywords
This publication has 23 references indexed in Scilit:
- Improved algorithms for graph four- connectivityJournal of Computer and System Sciences, 1991
- Fully dynamic algorithms for edge connectivity problemsPublished by Association for Computing Machinery (ACM) ,1991
- Algorithms for parallel k-vertex connectivity and sparse certificatesPublished by Association for Computing Machinery (ACM) ,1991
- Maintaining Bridge-Connected and Biconnected Components On-LinePublished by Defense Technical Information Center (DTIC) ,1989
- A topological approach to dynamic graph connectivityInformation Processing Letters, 1987
- Dynamic orthogonal segment intersection searchJournal of Algorithms, 1987
- Finding the Vertex Connectivity of GraphsSIAM Journal on Computing, 1980
- Dividing a Graph into Triconnected ComponentsSIAM Journal on Computing, 1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- Non-separable and planar graphsTransactions of the American Mathematical Society, 1932