Hamiltonian Path Problems on Distance-Hereditary Graphs

Abstract

A Hamiltonian path of a graph G with respect to a subset T of vertices, |T | ≤ 2, is a Hamiltonian path P of G such that vertices in T are end vertices of P. Given a graph G and a subset T of vertices, the constrained Hamiltonian path problem involves testing whether a Hamiltonian path of G with respect to T exists. Hamiltonian path problem is the special constrained Hamiltonian path problem where T is empty. A connected graph G = (V,E) is distance-hereditary if every two vertices in V have the same distance in every connected induced subgraph of G containing them. This paper presents linear time algorithms for the constrained Hamiltonian path problems on distance-hereditary graphs whereas the best previous known algorithm for Hamiltonian path problem on distance-hereditary graphs runs in O(|V |5) time.