×

zbMATH — the first resource for mathematics

Certifying 3-edge-connectivity. (English) Zbl 1356.05150
Summary: We present a certifying algorithm that tests graphs for 3-edge-connectivity; the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a 2-edge-cut. If it is 3-edge-connected, it returns a construction sequence that constructs the input graph from the graph with two vertices and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity. Additionally, we show how to compute and certify the 3-edge-connected components and a cactus representation of the 2-cuts in linear time. For 3-vertex-connectivity, we show how to compute the 3-vertex-connected components of a 2-connected graph.

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C40 Connectivity
Software:
AutoCorres; LEDA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alkassar, E; Böhme, S; Mehlhorn, K; Rizkallah, Ch, A framework for the verification of certifying computations, J. Autom. Reason., 52, 241-273, (2014) · Zbl 1314.68180
[2] Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, Berlin (2008) · Zbl 1134.05001
[3] Corcoran, JN; Schneider, U; Schüttler, H-B, Perfect stochastic summation in high order Feynman graph expansions, Int. J. Mod. Phys. C, 17, 1527-1549, (2006) · Zbl 1121.82327
[4] Dehne, F., Langston, M., Luo, X., Pitre, S., Shaw, P., Zhang, Y.: The cluster editing problem: implementations and experiments. In: Parameterized and Exact Computation, pp. 13-24 (2006) · Zbl 1154.68451
[5] Dinits, E.A., Karzanov, A.V., Lomonosov, M.V.: On the structure of a family of minimal weighted cuts in graphs. In: Studies in Discrete Mathematics (in Russian), pp. 290-306 (1976)
[6] Fleiner, T., Frank, A.: A quick proof for the cactus representation of mincuts. Technical Report QP-2009-03, Egerváry Research Group, Budapest (2009) · Zbl 1259.05173
[7] Gabow, HN, Path-based depth-first search for strong and biconnected components, Inf. Process. Lett., 74, 107-114, (2000) · Zbl 1339.68301
[8] Galil, Z; Italiano, GF, Reducing edge connectivity to vertex connectivity, SIGACT News, 22, 57-61, (1991)
[9] Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Proceedings of the 8th International Symposium on Graph Drawing (GD’00), pp. 77-90 (2001) · Zbl 1043.68621
[10] Hopcroft, J; Tarjan, R, Efficient planarity testing, J. ACM, 21, 549-568, (1974) · Zbl 0307.68025
[11] Hopcroft, JE; Tarjan, RE, Dividing a graph into triconnected components, SIAM J. Comput., 2, 135-158, (1973) · Zbl 0281.05111
[12] Karger, DR, Minimum cuts in near-linear time, J. ACM, 47, 46-76, (2000) · Zbl 1094.68613
[13] Linial, N; Lovász, L; Wigderson, A, Rubber bands, convex embeddings and graph connectivity, Combinatorica, 8, 91-102, (1988) · Zbl 0674.05046
[14] Lovász, L.: Computing ears and branchings in parallel. In: Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS’85) (1985) · Zbl 1298.68289
[15] Mader, W.: A reduction method for edge-connectivity in graphs. In: Bollobás, B. (ed.) Advances in Graph Theory, vol. 3 of Annals of Discrete Mathematics, pp. 145-164 (1978) · Zbl 0389.05042
[16] McConnell, RM; Mehlhorn, K; Näher, S; Schweitzer, P, Certifying algorithms, Comput. Sci. Rev., 5, 119-161, (2011) · Zbl 1298.68289
[17] Mehlhorn, K, Nearly optimal binary search trees, Acta Inform., 5, 287-295, (1975) · Zbl 0333.68028
[18] Mehlhorn, K., Näher, S., Uhrig, C.: The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999) · Zbl 0976.68156
[19] Nagamochi, H; Ibaraki, T, A linear time algorithm for computing 3-edge-connected components in a multigraph, Jpn. J. Ind. Appl. Math., 9, 163-180, (1992) · Zbl 0761.05089
[20] Nagamochi, H., Ibaraki, T.: Algorithmic Aspects of Graph Connectivity (Encyclopedia of Mathematics and its Applications). Cambridge University Press, Cambridge (2008) · Zbl 1172.05003
[21] Neumann, A.: Implementation of Schmidt’s algorithm for certifying triconnectivity testing. Master’s thesis, Universität des Saarlandes and Graduate School of CS, Germany (2011) · Zbl 0307.68025
[22] Noschinski, L., Rizkallah, C., Mehlhorn, K.: Verification of certifying computations through Autocorres and Simpl. In: NASA Formal Methods, vol. 8430 of LNCS, pp. 46-61 (2014)
[23] Olariu, S; Zomaya, AY, A time- and cost-optimal algorithm for interlocking sets-with applications, IEEE Trans. Parallel Distrib. Syst., 7, 1009-1025, (1996)
[24] Ramachandran, V.: Parallel open ear decomposition with applications to graph biconnectivity and triconnectivity. In: Synthesis of Parallel Algorithms, pp. 275-340 (1993) · Zbl 1339.68301
[25] Schmidt, J.M.: Contractions, removals and certifying 3-connectivity in linear time. Tech. Report B 10-04, Freie Universität Berlin, Germany (2010) · Zbl 1271.68242
[26] Schmidt, JM, Contractions, removals and certifying 3-connectivity in linear time, SIAM J. Comput., 42, 494-535, (2013) · Zbl 1271.68242
[27] Schmidt, JM, A simple test on 2-vertex- and 2-edge-connectivity, Inf. Process. Lett., 113, 241-244, (2013) · Zbl 1259.05173
[28] Taoka, S; Watanabe, T; Onaga, K, A linear time algorithm for computing all 3-edge-connected components of a multigraph, IEICE Trans. Fundam., E75, 410-424, (1992)
[29] Tsin, YH, A simple 3-edge-connected component algorithm, Theory Comput. Syst., 40, 125-142, (2007) · Zbl 1107.68069
[30] Tsin, YH, Yet another optimal algorithm for 3-edge-connectivity, J. Discrete Algorithms, 7, 130-146, (2009) · Zbl 1168.68613
[31] Vo, K-P, Finding triconnected components of graphs, Linear Multilinear Algebra, 13, 143-165, (1983) · Zbl 0514.05039
[32] Vo, K-P, Segment graphs, depth-first cycle bases, 3-connectivity, and planarity of graphs, Linear Multilinear Algebra, 13, 119-141, (1983) · Zbl 0514.05029
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.