id,collection,dc.contributor.author[],dc.contributor.institution[],dc.date.accessioned[],dc.date.available[],dc.date.issued[],dc.description.abstract[de],dc.format.extent[],dc.identifier.uri,dc.identifier.uri[],dc.language[],dc.relation.ispartofseries[],dc.rights.uri[],dc.subject.ddc[],dc.title[],dc.type[],dcterms.accessRights.openaire,refubium.affiliation.other[],refubium.affiliation[de],refubium.mycore.derivateId[],refubium.mycore.fudocsId[],refubium.series.name,refubium.series.reportNumber "add36a2c-ad31-48c4-9add-a25759f35aa6","fub188/17746","Schmidt, Jens M.","FU Berlin","2018-06-08T07:33:08Z","2010-05-31","2010","As 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.","18 S.","http://dx.doi.org/10.17169/refubium-21905","https://refubium.fu-berlin.de/handle/fub188/18196","eng","urn:nbn:de:kobv:188-fudocsseries000000000021-2","http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen","000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik","Contractions, removals and certifying 3-connectivity in linear time","Buch","open access","Institut für Informatik / Theoretische Informatik:::cc2346f5-5412-40f2-82fa-c99c6bb4233c:::600","Mathematik und Informatik","FUDOCS_derivate_000000000934","FUDOCS_document_000000005467","Freie Universität Berlin, Fachbereich Mathematik und Informatik","10-4"