An O(n+ m) certifying triconnnectivity algorithm for Hamiltonian graphs

Publikationstyp
Journal Article
Date Issued
2010-12-08
Sprache
English
Author(s)
Elmasry, Amr  
Mehlhorn, Kurt  
Schmidt, Jens M.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/7641
Journal
Algorithmica  
Volume
62
Issue
3-4
Start Page
754
End Page
766
Citation
Algorithmica (2012)
Publisher DOI
10.1007/s00453-010-9481-2
Scopus ID
2-s2.0-78649715992
Publisher
Springer
A graph is triconnected if it is connected, has at least 4 vertices and the removal of any two vertices does not disconnect the graph. We give a certifying algorithm deciding triconnectivity of Hamiltonian graphs with linear running time (this assumes that the cycle is given as part of the input). If the input graph is triconnected, the algorithm constructs an easily checkable proof for this fact. If the input graph is not triconnected, the algorithm returns a separation pair.
Subjects
Certifying algorithms
Graph algorithms
Hamiltonian graph
Triconnectivity
DDC Class
510: Mathematik