The Longest Path Problem Is Polynomial on Interval Graphs

DOI10.1007/978-3-642-03816-7_35zbMath1250.68128MaRDI QIDQ3182942

Kyriaki Ioannidou, George B. Mertzios, Stavros D. Nikolopoulos

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/9296/1/9296.pdf

zbMATH Keywords

complexity; dynamic programming; polynomial algorithm; interval graphs; longest path problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Longest (s, t)-paths in L-shaped grid graphs, Tropical paths in vertex-colored graphs, An approximation algorithm for the longest cycle problem in solid grid graphs, A linear-time algorithm for the longest path problem in rectangular grid graphs, The longest cycle problem is polynomial on interval graphs, A genetic algorithm for the picture maze generation problem, Sitting closer to friends than enemies, revisited, The Longest Path Problem is Polynomial on Cocomparability Graphs, A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximating the longest path in a graph
• Algorithms for long paths in graphs
• Linear algorithm for optimal path cover problem on interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Finding Hamiltonian circuits in interval graphs
• A unified approach to domination problems on interval graphs
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Paths in interval graphs and circular arc graphs
• On computing a longest path in a tree
• The Hamiltonian circuit problem for circle graphs is NP-complete
• Algorithmic graph theory and perfect graphs
• HAMILTONian circuits in chordal bipartite graphs
• Linear structure of bipartite permutation graphs and the longest path problem
• Finding paths and cycles of superpolylogarithmic length
• Finding Long Paths, Cycles and Circuits
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Hamilton Paths in Grid Graphs
• Algorithms and Computation