Algorithms for long paths in graphs

DOI10.1016/j.tcs.2007.02.012zbMath1117.68057OpenAlexW2004084580MaRDI QIDQ884457

Zhao Zhang, Hao Li

Publication date: 6 June 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.012

zbMATH Keywords

Hamiltonianlong pathneighborhood condition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The Longest Path Problem Is Polynomial on Interval Graphs ⋮ The longest path problem is polynomial on cocomparability graphs ⋮ The longest path problem has a polynomial solution on interval graphs ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ Algorithm for two disjoint long paths in 2-connected graphs ⋮ The Longest Path Problem is Polynomial on Cocomparability Graphs ⋮ A genetic algorithm for the picture maze generation problem ⋮ Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs ⋮ A linear-time algorithm for the longest path problem in rectangular grid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximating the longest path in a graph
• Hamiltonism, degree sum and neighborhood intersections
• Longest cycles in 3-connected graphs
• Color-coding
• Finding long paths and cycles in sparse Hamiltonian graphs
• Note on Hamilton Circuits
• On Linear Time Minor Tests with Depth-First Search
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
• Finding a Path of Superlogarithmic Length
• Some Theorems on Abstract Graphs
• Combinatorial optimization. Theory and algorithms