For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Longest Path Problems on Ptolemaic Graphs
Yoshihiro TAKAHARA Sachio TERAMOTO Ryuhei UEHARA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2008/02/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithms
dynamic programming, Hamiltonian path/cycle problem, longest path/cycle problem, Ptolemaic graphs,
Full Text: PDF(252.6KB)
>>Buy this Article
Longest path problem is a problem for finding a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, there are few known graph classes such that the longest path problem can be solved efficiently. Polynomial time algorithms for finding a longest cycle and a longest path in a Ptolemaic graph are proposed. Ptolemaic graphs are the graphs that satisfy the Ptolemy inequality, and they are the intersection of chordal graphs and distance-hereditary graphs. The algorithms use the dynamic programming technique on a laminar structure of cliques, which is a recent characterization of Ptolemaic graphs.