DB2 and DB2A: Two useful tools for constructing Hamiltonian circuits

DOI10.1016/0377-2217(88)90357-8MaRDI QIDQ1092923zbMATH OpenOpenAlexFDO

Authors Francesco A. Brunacci

Publication date 1988

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(88)90357-8

zbMATH Keywords

DB2Adirected graphHamiltonian circuitnetworks

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to combinatorics (05-04) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Review text

The paper presents a procedure, called DB2A, for constructing a Hamiltonian circuit (HC) in a general directed graph. Application examples and a completely developed example problem are included. An appendix recalls the features of DB2, used here as a subprocedure of DB2A, and finding a Hamiltonian cycle in undirected graphs.

Recommendations

• Enumeration of Hamiltonian circuits in digraphs
• A heuristic method for the determination of a Hamiltonian circuit in a graph
• scientific article; zbMATH DE number 1192948
• On the construction and enumeration of Hamiltonian graphs
• An algorithm for finding hamilton cycles in random directed graphs

Cites work

• A useful transform of standard input data for a classical NP-complete problem
• An efficient collision-free protocol for prioritized access-control of cable or radio channels
• scientific article; zbMATH DE number 3950233 (Why is no real title available?)
• scientific article; zbMATH DE number 3503127 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• On the length of optimal TSP circuits in sets of bounded diameter
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• The NP-completeness column: An ongoing guide

Cited in

(4)

• HybridHAM: a novel hybrid heuristic for finding Hamiltonian cycle
• Hamiltonian cycle curves in the space of discounted occupational measures
• Enumeration of Hamiltonian circuits in digraphs
• A heuristic method for the determination of a Hamiltonian circuit in a graph

This page was built for publication: DB2 and DB2A: Two useful tools for constructing Hamiltonian circuits

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