Certifying 3-edge-connectivity

Publikationstyp
Conference Paper
Date Issued
2013
Sprache
English
Author(s)
Mehlhorn, Kurt  
Neumann, Adrian  
Schmidt, Jens M.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/7655
First published in
Lecture notes in computer science  
Number in series
8165 LNCS
Start Page
358
End Page
369
Citation
39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013)
Publisher DOI
10.1007/978-3-642-45043-3_31
Scopus ID
2-s2.0-84893153759
Publisher
Springer
We present a linear-time certifying algorithm that tests graphs for 3-edge-connectivity. If the input graph G is not 3-edge-connected, the algorithm returns a 2-edge-cut. If G is 3-edge-connected, the algorithm returns a construction sequence that constructs G from the graph with two nodes and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity.
DDC Class
004: Informatik