Dokumentenserver der Freien Universität Berlin

Objekt-Metadaten

Contractions, removals and certifying 3-connectivity in linear time
Schmidt, Jens M. ;  FU Berlin ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

HaupttitelContractions, removals and certifying 3-connectivity in linear time
AutorSchmidt, Jens M.
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl18 S.
Schriftenreihe Technical report B ; 10-04
DDC004 Datenverarbeitung; Informatik
ZusammenfassungAs existence result, it is well known that every 3-connected graph G=(V,E) on more than 4 vertices admits a sequence of contractions and a sequence of removal operations to K_4 such that every intermediate graph in the sequences is 3-connected. We show that both sequences can be computed in linear time, improving the previous best known running time of O(|V|^2) to O(|V|+|E|). This settles also the open question of finding a certifying 3-connectivity test in linear time and extents to certify 3-edge-connectivity in linear time as well.
Dokumente
pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
 
Fachbereich/EinrichtungFB Mathematik und Informatik
Arbeitsbereich/InstitutTheoretische Informatik
Erscheinungsjahr2010
Dokumententyp/-SammlungenBuch
SpracheEnglisch
Rechte Nutzungsbedingungen
Erstellt am31.05.2010 - 11:11:06
Letzte Änderung23.01.2014 - 16:21:39
 
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000005467
Zugriffsstatistik