Improved algorithms for graph four-connectivity. (English) Zbl 0731.68086
Summary: We present a new algorithm based on open ear decomposition for testing vertex four-connectivity and for finding all separating triplets in a triconnected graph. A sequential implementation of our algorithm runs in \(O(n^ 2)\) time and a parallel implementation runs in \(O(\log^ 2n)\) time using \(O(n^ 2)\) processors on an ARBITRARY CRCW PRAM, where n is the number of vertices in the graph. This improves previous bounds for the problem for both the sequential and the parallel cases. The sequential time bound is the best possible to within a constant factor, if the input is specified in adjacency matrix form, or if the input graph is dense.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Becker, M.; Degenhardt, W.; Doenhardt, J.; Hertel, S.; Kaninke, G.; Keber, W.; Mehlhorn, K.; Naher, S.; Rohnert, H.; Winter, T., A probabilistic algorithm for vertex connectivity of graphs, Inform. Process. Lett., 15, No. 3, 135-136 (1982) · Zbl 0491.68066 |
| [2] | Cole, R., Parallel merge sort, (Proceedings, 27th IEEE Ann. Symp. on Foundations of Comp. Sci. (1986)), 511-516 |
| [3] | Even, S., Graph Algorithms (1979), Computer Science Press: Computer Science Press Rockville, MD · Zbl 0441.68072 |
| [4] | Even, S., An algorithm for determining whether the connectivity of a graph is at least \(k\), SIAM J. Comput., 4, 393-396 (1975) · Zbl 0311.05133 |
| [5] | Even, S.; Tarjan, R. E., Network flow and testing graph connectivity, SIAM J. Comput., 4, 507-518 (1975) · Zbl 0328.90031 |
| [6] | Galil, Z., Finding the vertex connectivity of graphs, SIAM J. Comput., 9, 197-199 (1980) · Zbl 0446.68053 |
| [7] | Girkar, M.; Sohoni, M., On Finding the Vertex Connectivity of Graphs, (Tech. Report ACT-77 (May 1987), Coordinated Science Laboratory, University of Illinois: Coordinated Science Laboratory, University of Illinois Urbana, II) |
| [8] | Hopcroft, J. E.; Tarjan, R. E., Dividing a graph into triconnected components, SIAM J. Comput., 135-158 (1973) · Zbl 0281.05111 |
| [9] | Kanevsky, A., On the Number of Minimum Size Separating Vertex Sets in a Graph, (Tech. Report ACT-80 (July 1987), Coordinated Science Laboratory, University of Illinois: Coordinated Science Laboratory, University of Illinois Urban, IL) · Zbl 0800.68633 |
| [10] | Kanevsky, A.; Ramachandran, V., Improved algorithms for graph four-connectivity, (Proceedings, 28th Ann. IEEE Symp. on Foundations of Comp. Sci. (1987)), 252-259 |
| [11] | Karp, R. M.; Ramachandran, V., Parallel algorithms for shared memory machines, (Handbook of Theoretical Computer Science (1990), North-Holland: North-Holland Amsterdam), 869-941 · Zbl 0900.68267 |
| [12] | Linial, N.; Lovasz, L.; Wigderson, A., A physical interpretation of graph connectivity, and its algorithm applications, (Proceedings, 27th IEEE Ann. Symp. on Foundations of Comp. Sci. (1986)), 39-48 |
| [13] | Lovasz, L., Computing ears and branchings in parallel, (Proceedings 26th IEEE Ann. Symp. on Foundations of Comp. Sci. (1985)), 464-467 |
| [14] | Matula, D., Determining edge connectivity in O(nm), (Proceedings, 28th IEEE Ann. Symp. on Foundations of Comp. Sci.. Proceedings, 28th IEEE Ann. Symp. on Foundations of Comp. Sci., Los Angeles, CA (1987)), 252-259 |
| [15] | Maon, Y.; Schieber, B.; Vishkin, U., Parallel ear decomposition search (EDS) and st-numbering in graphs, (VLSI Algorithms and Architectures. VLSI Algorithms and Architectures, Lecture Notes in Computer Science, Vol. 277 (1986)), 34-45 · Zbl 0595.68056 |
| [16] | Miller, G. L.; Ramachandran, V., Efficient parallel ear decomposition with applications (January 1986), MSRI: MSRI Berkeley, CA, manuscript |
| [17] | Miller, G. L.; Ramachandran, V., A new graph triconnectivity algorithm and its parallelization, (Proceedings, 19th ACM Ann. Symp. on Theory of Computing. Proceedings, 19th ACM Ann. Symp. on Theory of Computing, New York, NY (1987)), 335-344 |
| [18] | Ramachandran, V.; Vishkin, U., Efficient parallel triconnectivity in logarithmic time,, (VLSIAlgorithms and Architectures, AWOC88, Vol. 319 (1988), Springer-Verlag LNCS), 33-42 · Zbl 0649.68070 |
| [19] | Tarjan, R. E., Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 146-160 (1972) · Zbl 0251.05107 |
| [20] | Tarjan, R. E.; Vishkin, U., An efficient parallel biconnectivity algorithm, SIAM J. Comput., 14, 862-874 (1985) · Zbl 0575.68066 |
| [21] | Whitney, H., Non-separable and planar graphs, Trans. Amer. Math. Soc., 34, 339-362 (1932) · JFM 58.0608.01 |
| [22] | Fussell, D.; Ramachandran, V.; Thurimella, R., Finding triconnected components by local replacements, (ICALP 89. ICALP 89, Lecture Notes in Computer Science, Vol. 372 (1989)), 379-393 |
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.
