A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph. (English) Zbl 0763.05065
The authors present a linear-time algorithm for finding a sparse \(k\)- connected spanning subgraph for a given \(k\)-connected undirected graph. This is used to improve the time complexities of other graph connectivity problems.
Reviewer: H.T.Lau (Verdun / Quebec)
MSC:
| 05C40 | Connectivity |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
\(k\)-connected spanning subgraph; linear-time algorithm; time complexities; graph connectivity problemsReferences:
| [1] | Even, S.; Tarjan, R. E., Network flow and testing graph connectivity, SIAM J. Comput., 4, 507-518 (1975) · Zbl 0328.90031 · doi:10.1137/0204043 |
| [2] | Galil, Z., Finding the vertex connectivity of graphs, SIAM J. Comput., 9, 197-199 (1980) · Zbl 0446.68053 · doi:10.1137/0209016 |
| [3] | Garey, M. R.; Jhonson, D. S., Computer and Intractability, A Guide to the Theory of NP-completeness (1979), San Francisco: Freeman, San Francisco · Zbl 0411.68039 |
| [4] | D. W. Matula, Determining edge connectivity inO(nm),Proceedings of the 28th Symposium on Foundations of Computer Science (1987), pp. 249-251. |
| [5] | H. Nagamochi and T. Ibaraki, Linear time algorithms for findingk-edge-connected andk-node-connected spanning subgraphs, Technical Report #89006, Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University (1989). |
| [6] | H. Nagamochi and T. Ibaraki, Computing edge-connectivity in multiple and capacitated graphs, Technical Report # 89009, Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University (1989). · Zbl 0754.05062 |
| [7] | H. Nagamochi, Z. Sun, and T. Ibaraki, Counting the number of minimum cuts in multiple undirected graphs, Technical Report #89010, Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University (1989). · Zbl 0739.90026 |
| [8] | T. Nishizeki and S. Poljak, Highly connected factors with a small number of edges, Working Paper (1989). |
| [9] | H. Suzuki, N. Takahashi, and T. Nishizeki, An algorithm for finding a triconnected spanning subgraph, SIGAL Research Report 7-3 (in Japanese) (1989). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
