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

Main titleContractions, removals and certifying 3-connectivity in linear time
AuthorSchmidt, Jens M.
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages18 S.
Series Technical report B ; 10-04
Classification (DDC)004 Data processing and Computer science
AbstractAs 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.
Documents
pdf-Datei
If your browser can't open the file, please download the file first and then open it
 
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Theoretische Informatik
Year of publication2010
Type of documentBook
LanguageEnglish
Terms of use/Rights Nutzungsbedingungen
Created at2010-05-31 : 11:11:06
Last changed2014-01-23 : 04:21:39
 
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000005467
Statistics
 

LOADING...