IEICE Transactions on Information and Systems

IEICE Transactions on Information and Systems 2008 E91-D(2):170-177; doi:10.1093/ietisy/e91-d.2.170

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by TAKAHARA, Y. Articles by UEHARA, R. Search for Related Content Social Bookmarking          What's this?

Copyright © 2008 The Institute of Electronics, Information and Communication Engineers

Special Section on Foundations of Computer Science -- Papers -- Graph Algorithms

Longest Path Problems on Ptolemaic Graphs^*

Yoshihiro TAKAHARA^1,2, Sachio TERAMOTO^1,3 and Ryuhei UEHARA¹

¹ The authors are with School of Information Science, JAIST, Nomi-shi, 923–1292 Japan. E-mail: uehara{at}jaist.ac.jp, ² Presently, with Sekisui House., ³ Presently, with Service Platforms Research Laboratories, NEC Corporation.

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.

Key Words: dynamic programming, Hamiltonian path/cycle problem, longest path/cycle problem, Ptolemaic graphs

---

Manuscript received March 27, 2007. Manuscript revised June 18, 2007.

^* An extended abstract was presented at KyotoCGGT 2007. The authors are partially supported by the Ministry, Grant-in-Aid for Scientific Research (C).

Reference

[1] M. Garey and D. Johnson, Computers and Intractability — A Guide to the Theory of NP-Completeness, Freeman, 1979.

[2] D. Karger, R. Motwani, and G. Ramkumar, "On approximating the longest path in a graph," Algorithmica, vol.18, pp.82–98, 1997.

[3] H.N. Gabow, "Finding paths and cycles of superpolylogarithmic length," Proc. 36th Symp. on Foundations of Computer Science, pp.407–416, IEEE, 2004.

[4] S. Vishwanathan, "An approximation algorithm for finding a long path in Hamiltonian graphs," Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp.680–685, ACM, 2000.

[5] A. Björklund and T. Husfeldt, "Finding a path of superlogarithmic length," SIAM J. Comput., vol.32, no.6, pp.1395–1402, 2003.

[6] T. Feder and R. Motwani, "Finding large cycles in Hamiltonian graphs," Proc. 16th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp.166–175, ACM, 2005.

[7] R. Bulterman, F. van der Sommen, G. Zwaan, T. Verhoeff, A. van Gasteren, and W. Feijen, "On computing a longest path in a tree," Inf. Process. Lett., vol.81, pp.93–96, 2002.

[8] R. Uehara and Y. Uno, "Efficient algorithms for the longest path problem," 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004), Lecture Notes in Computer Science, vol.3341, pp.871–883, Springer-Verlag, 2004.

[9] H. Ito, Personal communication, 2004.

[10] R. Uehara and Y. Uno, "Laminar structure of ptolemaic graphs and its applications," 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), Lecture Notes in Computer Science, vol.3827, pp.186–195, Springer-Verlag, 2005.

[11] H. Müller, "Hamiltonian circuit in chordal bipartite graphs," Disc. Math., vol.156, pp.291–298, 1996.

[12] M. Chang, S. Wu, G. Chang, and H. Yeh, "Hamiltonian problems on ptolemaic graphs," Proc. Workshop on Algorithms and Theory of Computation, International Computer Symposium (ICS'00), pp.27–34, Taiwan, 2000.

[13] R.W. Hung, S.C. Wu, and M.S. Chang, "Hamiltonian cycle problem on distance-hereditary graphs," Journal of Information Science and Engineering, vol.19, pp.827–838, 2003.

[14] R.W. Hung and M.S. Chang, "Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs," Theor. Comput. Sci., vol.341, pp.411–440, 2005.

[15] S.Y. Hsieh, C.W. Ho, T.S. Hsu, and M.T. Ko, "The Hamiltonian problem on distance-hereditary graphs," Discrete Appl. Math., vol.154, pp.508–524, 2006.

[16] H.J. Bandelt and H. Mulder, "Distance-hereditary graphs," Journal of Combinatorial Theory, Series B, vol.41, pp.182–208, 1986.

[17] E. Howorka, "A characterization of ptolemaic graphs," Journal of Graph Theory, vol.5, pp.323–331, 1981.

[18] R. Uehara and Y. Uno, "On the laminar structure of ptolemaic and distance hereditary graphs," Complexity Seminar (Informal seminar in Japanese); available at http://www.jaist.ac.jp/~uehara/pdf/ptolemaic.pdf, March 2005.

CiteULike    Connotea    Del.icio.us    What's this?

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by TAKAHARA, Y. Articles by UEHARA, R. Search for Related Content Social Bookmarking          What's this?