An approximation algorithm for finding long paths in Hamiltonian graphs

DOI10.1016/S0196-6774(03)00093-2zbMATH Open1067.68110OpenAlexW4252035792MaRDI QIDQ4820883FDOQ4820883

Authors: Sundar Vishwanathan 

Publication date: 1 October 2004

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0196-6774(03)00093-2

Recommendations

• scientific article; zbMATH DE number 1445365
• Finding long paths and cycles in sparse Hamiltonian graphs
• On approximating the longest path in a graph
• An extension of the multi-path algorithm for finding Hamilton cycles
• An algorithm for finding Hamilton paths and cycles in random graphs
• Approximation algorithms for multiple terminal, Hamiltonian path problems
• Algorithms for the optimal Hamiltonian path in Halin graphs
• On approximating the longest path in a graph
• Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs
• Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Eulerian and Hamiltonian graphs (05C45)

Cited In (9)

• On approximating the longest path in a graph
• Finding long paths and cycles in sparse Hamiltonian graphs
• Approximating long cycle above Dirac's guarantee
• Title not available (Why is that?)
• On approximating the longest path in a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• A successful algorithm for solving directed Hamiltonian path problems
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm

This page was built for publication: An approximation algorithm for finding long paths in Hamiltonian graphs

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