An O(n+m) Certifying Triconnnectivity Algorithm for Hamiltonian Graphs | Zendy

Amr Elmasry | Zendy; Kurt Mehlhorn | Zendy; Jens M. Schmidt | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

An O(n+m) Certifying Triconnnectivity Algorithm for Hamiltonian Graphs

Author(s) -

Amr Elmasry,

Kurt Mehlhorn,

Jens M. Schmidt

Publication year - 2010

Publication title -

algorithmica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.647

H-Index - 78

eISSN - 1432-0541

pISSN - 0178-4617

DOI - 10.1007/s00453-010-9481-2

Subject(s) - theory of computation , algorithm , combinatorics , hamiltonian path problem , computer science , hamiltonian (control theory) , mathematics , discrete mathematics , hamiltonian path , graph , mathematical optimization

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research