English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Certifying 3-Edge-Connectivity

MPS-Authors
/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons71827

Neumann,  Adrian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons118275

Schmidt,  Jens M.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

1211.6553.pdf
(Preprint), 4KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Mehlhorn, K., Neumann, A., & Schmidt, J. M. (2013). Certifying 3-Edge-Connectivity. Retrieved from http://arxiv.org/abs/1211.6553.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-A622-F
Abstract
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 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.