A successful algorithm for solving directed Hamiltonian path problems

DOI10.1016/0167-6377(84)90069-5MaRDI QIDQ788642zbMATH OpenOpenAlexFDO

Authors G. L. Thompson, Sharad Singhal

Publication date 1984

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(84)90069-5

zbMATH Keywords

Hamiltonian pathramification indexComputational experiencegraph-theoretic polynomial algorithmspanning arborescences

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Recommendations

• A successful algorithm for the undirected Hamiltonian path problem
• A SAT based effective algorithm for the directed Hamiltonian cycle problem
• An effective algorithm for and phase transitions of the directed Hamiltonian cycle problem
• Algorithms for the optimal Hamiltonian path in Halin graphs
• Publication:4952685
• A note on the Hamiltonian circuit problem on directed path graphs
• An approximation algorithm for finding long paths in Hamiltonian graphs
• A simple linear expected time algorithm for finding a Hamilton path
• Publication:4036583
• An efficient algorithm for constructing Hamiltonian paths in meshes

Cites work

• scientific article; zbMATH DE number 3427118 (Why is no real title available?)
• scientific article; zbMATH DE number 3503127 (Why is no real title available?)
• scientific article; zbMATH DE number 3575371 (Why is no real title available?)
• A LIFO implicit enumeration algorithm for the asymmetric travelling salesman problem using a one-arborescence relaxation
• Algorithms for Large-scale Travelling Salesman Problems
• Graph theory
• Hamiltonian Tours and Paths in Rectangular Lattice Graphs
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Topological design of centralized computer networks—formulations and algorithms

Cited in

(10)

• Time-free solution to Hamilton path problems using P systems with \(d\)-division
• A simple linear expected time algorithm for finding a Hamilton path
• Algorithms for Page Retrieval and Hamiltonian Paths on Forward-Convex Line Graphs
• A successful algorithm for the undirected Hamiltonian path problem
• scientific article; zbMATH DE number 3917709 (Why is no real title available?)
• A SAT based effective algorithm for the directed Hamiltonian cycle problem
• Expected Computation Time for Hamiltonian Path problem
• An effective algorithm for and phase transitions of the directed Hamiltonian cycle problem
• A randomized parallel branch-and-bound algorithm
• A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs

This page was built for publication: A successful algorithm for solving directed Hamiltonian path problems

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