Longest Path Problems on Ptolemaic Graphs
Longest Path Problems on Ptolemaic Graphs
复制标题
DOI：
10.1093/ietisy/e91-d.2.170
复制
发表时间：
2008-02
期刊：
影响因子：
--
通讯作者：
Y. Takahara;S. Teramoto;Ryuhei Uehara
中科院分区：
文献类型：
--
作者：
Y. Takahara;S. Teramoto;Ryuhei Uehara
最长路问题是在给定的图中寻找最长路的问题。虽然图类中的哈密尔顿路径问题可以有效地解决了广泛的调查，有几个已知的图类，使最长路径问题可以有效地解决。提出了求托勒密图中最长圈和最长路的多项式时间算法。托勒密图是满足托勒密不等式的图，是弦图和距离遗传图的交集。该算法使用动态规划技术的层状结构的团，这是最近的表征托勒密图。
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.