Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
  Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben
Forschungspapier

Certifying 3-Edge-Connectivity

MPG-Autoren
/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;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

1211.6553.pdf
(Preprint), 4KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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


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