Navigation/Menü: Links auf weitere Seiten dieser Website
Objekt-Metadaten
| Contractions, removals and certifying 3-connectivity in linear time Schmidt, Jens M. |
| Haupttitel | Contractions, removals and certifying 3-connectivity in linear time |
| Autor | Schmidt, Jens M. |
| Institution/Körperschaft | FU Berlin |
| Seitenzahl | 18 S. |
| Schriftenreihe | Technical report B ; 10-04 |
| Fachbereich/Einrichtung | FB Mathematik und Informatik |
| Arbeitsbereich/Institut | Theoretische Informatik |
| Erscheinungsjahr | 2010 |
| Dokumente | pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
|
| DDC | 004 Datenverarbeitung; Informatik |
| Dokumententyp/-Sammlungen | Monographie/Text |
| Medientyp/Format | Text |
| Abstract | 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. |
| Sprache | Englisch |
| Rechte | Nutzungsbedingungen |
| Zugriffstatistik | |
| Statische URL | http://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000005467 |
| Erstellt am | 31.05.2010 - 13:11:06 |
| Letzte Änderung | 04.04.2013 - 09:33:30 |
