Longest Path Problems on Ptolemaic Graphs
-
- TAKAHARA Yoshihiro
- School of Information Science Presently, Sekisui House
-
- TERAMOTO Sachio
- School of Information Science Presently, Service Platforms Research Laboratories, NEC Corporation
-
- UEHARA Ryuhei
- School of Information Science The Institute of Electronics, Information and Communication Engineers
Search this article
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.
Journal
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E91-D (2), 170-177, 2008
The Institute of Electronics, Information and Communication Engineers
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1390001204379257856
-
- NII Article ID
- 10026800882
-
- NII Book ID
- AA10826272
-
- ISSN
- 17451361
- 09168532
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- IRDB
- Crossref
- CiNii Articles
-
- Abstract License Flag
- Disallowed