Algorithms for long paths in graphs

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

Hao Li, Zhao Zhang

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

Hamiltonian; long path; neighborhood condition

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

The longest path problem has a polynomial solution on interval graphs, Algorithm for two disjoint long paths in 2-connected graphs, The Longest Path Problem is Polynomial on Cocomparability Graphs, The Longest Path Problem Is Polynomial on Interval Graphs

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item