caa a22 4500 445805455 CHVBK 20180317145155.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00453-010-9411-3 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9411-3 The Longest Path Problem has a Polynomial Solution on Interval Graphs [Elektronische Daten] [Kyriaki Ioannidou, George Mertzios, Stavros Nikolopoulos] 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 (Proc. of the 15th Annual International Symp. on Algorithms and Computation (ISAAC), LNCS, vol.3341, pp.871-883, 2004), 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 uses a dynamic programming approach and runs in O(n 4) time, where n is the number of vertices of the input graph. Springer Science+Business Media, LLC, 2010 Longest path problem nationallicence Interval graphs nationallicence Polynomial algorithm nationallicence Complexity nationallicence Dynamic programming nationallicence Ioannidou Kyriaki Department of Computer Science, University of Ioannina, P.O. Box 1186, 45110, Ioannina, Greece aut Mertzios George Department of Computer Science, RWTH Aachen University, Ahornstr. 55, 52074, Aachen, Germany aut Nikolopoulos Stavros Department of Computer Science, University of Ioannina, P.O. Box 1186, 45110, Ioannina, Greece aut Algorithmica Springer-Verlag 61/2(2011-10-01), 320-341 0178-4617 61:2<320 2011 61 453 https://doi.org/10.1007/s00453-010-9411-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9411-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Ioannidou Kyriaki Department of Computer Science, University of Ioannina, P.O. Box 1186, 45110, Ioannina, Greece aut NATIONALLICENCE 700 1- Mertzios George Department of Computer Science, RWTH Aachen University, Ahornstr. 55, 52074, Aachen, Germany aut NATIONALLICENCE 700 1- Nikolopoulos Stavros Department of Computer Science, University of Ioannina, P.O. Box 1186, 45110, Ioannina, Greece aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/2(2011-10-01), 320-341 0178-4617 61:2<320 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer