The Longest Path Problem Is Polynomial on Interval Graphs

DOI10.1007/978-3-642-03816-7_35MaRDI QIDQ3182942zbMATH OpenOpenAlexFDO

Authors 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

dynamic programmingcomplexityinterval graphspolynomial algorithmlongest path problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)

Recommendations

• The longest path problem has a polynomial solution on interval graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• The longest path problem is polynomial on cocomparability graphs
• The longest cycle problem is polynomial on interval graphs
• The longest path problem is polynomial on cocomparability graphs

Cites work

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

Cited in

(20)

• An approximation algorithm for the longest cycle problem in solid grid graphs
• Tropical paths in vertex-colored graphs
• The longest cycle problem is polynomial on interval graphs
• Sitting closer to friends than enemies, revisited
• The longest path problem is polynomial on cocomparability graphs
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• An experimental study of ILP formulations for the longest induced path problem
• Longest (s, t)-paths in L-shaped grid graphs
• On computing longest paths in small graph classes
• A simple polynomial algorithm for the longest path problem on cocomparability graphs
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• A genetic algorithm for the picture maze generation problem
• The longest path problem is polynomial on cocomparability graphs
• The longest path problem has a polynomial solution on interval graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• The longest path problem in odd-sized \(O\)-shaped grid graphs
• A polynomial time algorithm for longest paths in biconvex graphs
• An algebraic approach to the longest path problem
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs

This page was built for publication: The Longest Path Problem Is Polynomial on Interval Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3182942)