The Longest Path Problem Is Polynomial on Interval Graphs
From MaRDI portal
Publication:3182942
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
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