TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publication References
  4. Certifying 3-connectivity in linear time
 
Options

Certifying 3-connectivity in linear time

Publikationstyp
Conference Paper
Date Issued
2012-12-01
Sprache
English
Author(s)
Schmidt, Jens M.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/7653
First published in
Lecture notes in computer science  
Number in series
7391 LNCS
Issue
PART 1
Start Page
786
End Page
797
Citation
International Colloquium on Automata, Languages, and Programming (ICALP 2012)
Publisher DOI
10.1007/978-3-642-31594-7_66
Scopus ID
2-s2.0-84883819250
One of the most noted construction methods of 3-vertex-connected graphs is due to Tutte and based on the following fact: Every 3-vertex-connected graph G on more than 4 vertices contains a contractible edge, i. e., an edge whose contraction generates a 3-connected graph. This implies the existence of a sequence of edge contractions from G to K 4 such that every intermediate graph is 3-vertex-connected. A theorem of Barnette and Grünbaum yields a similar sequence using removals of edges instead of contractions. We show how to compute both sequences in optimal time, improving the previously best known running times of O(|V|2) to O(|E|). Based on this result, we give a linear-time test of 3-connectivity that is certifying; finding such an algorithm has been a major open problem in the design of certifying algorithms in the last years. The 3-connectivity test is conceptually different from well-known linear-time tests of 3-connectivity; it uses a certificate that is easy to verify in time O(|E|). We also provide an optimal certifying test of 3-edge-connectivity.
DDC Class
004: Informatik
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback