K. Ioannidou
The longest path problem is polynomial on interval graphs
Ioannidou, K.; Mertzios, G.B.; Nikolopoulos, S.D.
Authors
Contributors
Královič Rastislav
Editor
Niwinski Damian
Editor
Abstract
The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian path problem. Motivated by the work of Uehara and Uno in [20], where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem can be solved in polynomial time on interval graphs. The proposed algorithm runs in O(n 4) time, where n is the number of vertices of the input graph, and bases on a dynamic programming approach.
Citation
Ioannidou, K., Mertzios, G., & Nikolopoulos, S. (2009). The longest path problem is polynomial on interval graphs. In K. Rastislav, & N. Damian (Eds.), Mathematical foundations of computer science 2009 34th international symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009 : proceedings (403-414). https://doi.org/10.1007/978-3-642-03816-7_35
Conference Name | 34st International Symposium on Mathematical Foundations of Computer Science (MFCS) |
---|---|
Conference Location | Novy Smokovec, Slovakia |
Publication Date | Aug 1, 2009 |
Deposit Date | Dec 8, 2011 |
Publicly Available Date | Mar 29, 2024 |
Pages | 403-414 |
Series Title | Lecture notes in computer science |
Series Number | 5734 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Mathematical foundations of computer science 2009 34th international symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009 : proceedings. |
DOI | https://doi.org/10.1007/978-3-642-03816-7_35 |
Keywords | Longest path problem, Interval graphs, Polynomial algorithm, Complexity, Dynamic programming. |
Public URL | https://durham-repository.worktribe.com/output/1157550 |
Additional Information | Proceedings published as: Mathematical Foundations of Computer Science 2009, 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Symposium url: http://www.mfcs.sk/mfcs2009/ |
Files
Accepted Conference Proceeding
(190 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-03816-7_35
You might also like
Graphs with minimum fractional domatic number
(2023)
Journal Article
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search