IEICE TRANSACTIONS on Information
Longest Path Problems on Ptolemaic Graphs
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E91-D No.2 pp.170-177
- Publication Date
- 2008/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e91-d.2.170
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- Category
- Graph Algorithms
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yoshihiro TAKAHARA, Sachio TERAMOTO, Ryuhei UEHARA, "Longest Path Problems on Ptolemaic Graphs" in IEICE TRANSACTIONS on Information,
vol. E91-D, no. 2, pp. 170-177, February 2008, doi: 10.1093/ietisy/e91-d.2.170.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e91-d.2.170/_p
Copy
@ARTICLE{e91-d_2_170,
author={Yoshihiro TAKAHARA, Sachio TERAMOTO, Ryuhei UEHARA, },
journal={IEICE TRANSACTIONS on Information},
title={Longest Path Problems on Ptolemaic Graphs},
year={2008},
volume={E91-D},
number={2},
pages={170-177},
abstract={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.},
keywords={},
doi={10.1093/ietisy/e91-d.2.170},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - Longest Path Problems on Ptolemaic Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 170
EP - 177
AU - Yoshihiro TAKAHARA
AU - Sachio TERAMOTO
AU - Ryuhei UEHARA
PY - 2008
DO - 10.1093/ietisy/e91-d.2.170
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E91-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2008
AB - 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.
ER -
English
