Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs

DOI10.1016/0020-0190(93)90100-NMaRDI QIDQ685527zbMATH OpenOpenAlexFDO

Authors Haiko Müller, Falk Nicolai

Publication date 15 December 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90100-n

zbMATH Keywords

Hamiltonian circuitspolynomial time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

By investigating the neighbourhood of the last pendant vertex in a one vertex extension-sequence we develop polynomial time algorithms for the problems Hamiltonian Circuit and Hamiltonian Path in (6,2)-chordal bipartite graphs.

Recommendations

• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• scientific article; zbMATH DE number 2089962
• The Hamiltonian problem on distance-hereditary graphs
• A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs
• Hamiltonian problem on claw-free and almost distance-hereditary graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• scientific article; zbMATH DE number 1303031
• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• The F-Hamiltonian problem for bipartite graphs

Cites work

• Chordality properties on graphs and minimal conceptual connections in semantic data models
• Completely separable graphs
• Distance-hereditary graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4045182 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)

Cited in

(8)

• A linear time recognition algorithm for proper interval graphs
• HAMILTONian circuits in chordal bipartite graphs
• Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs
• Equistable distance-hereditary graphs
• The Hamiltonian problem on distance-hereditary graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• A necessary and sufficient condition for a bipartite distance-hereditary graph to be Hamiltonian
• A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs

This page was built for publication: Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685527)