Reduced-by-matching graphs: toward simplifying Hamiltonian circuit problem

DOI10.3233/FI-2012-711MaRDI QIDQ2898470zbMATH OpenOpenAlexWikidataFDO

Authors Jacek Blazewicz, Marta Kasprzak

Publication date 11 July 2012

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2012-711

zbMATH Keywords

digraphsgraph reductionquasi-adjoint graphsHamiltonian circuit problemdirected line graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• A note on the Hamiltonian circuit problem on directed path graphs
• Finding Hamiltonian circuits in interval graphs
• On testing Hamiltonicity of graphs
• Enumeration of Hamiltonian circuits in digraphs
• An algorithm for finding hamilton cycles in random directed graphs

Cited in

(5)

• Beyond quasi-adjoint graphs: on polynomial-time solvable cases of the Hamiltonian cycle and path problems
• Graph algorithms for DNA sequencing -- origins, current models and the future
• Minimization procedure for Hamiltonian circuit and graph isomorphism problems
• scientific article; zbMATH DE number 682490 (Why is no real title available?)
• Classification of de Bruijn-based labeled digraphs

This page was built for publication: Reduced-by-matching graphs: toward simplifying Hamiltonian circuit problem

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