On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs

DOI10.1006/JAGM.1998.0998zbMATH Open0919.05039OpenAlexW2027410688MaRDI QIDQ4240135FDOQ4240135

Authors: Miklos Santha, Zsolt Tuza, Cristina Bazgan 

Publication date: 31 August 1999

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

Full work available at URL: https://semanticscholar.org/paper/3b98d5e3683614bedc3d3ee590095549cb4f64bb

Recommendations

• scientific article; zbMATH DE number 1445365
• The complexity of finding a second Hamiltonian cycle in cubic graphs
• Approximating the Longest Cycle Problem in Sparse Graphs
• The complexity of Thomason's algorithm for finding a second Hamiltonian cycle

zbMATH Keywords

complexityHamiltonian cyclelongest path problemcubic Hamiltonian graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cited In (24)

• Better approximations of non-Hamiltonian graphs
• Finding large cycles in Hamiltonian graphs
• Approximating the longest paths in grid graphs
• On the Power of Planned Infections in Networks
• Approximating long cycle above Dirac's guarantee
• Aspects of upper defensive alliances
• Hardness of bounding influence via graph modification
• Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
• Approximating Alternative Solutions
• Title not available (Why is that?)
• An approximation algorithm for the maximum spectral subgraph problem
• Hamiltonian cycles in subcubic graphs: what makes the problem difficult
• Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs
• Approximate and randomized algorithms for computing a second Hamiltonian cycle
• Simple algorithm for finding a second Hamilton cycle
• Title not available (Why is that?)
• A new heuristic for detecting non-Hamiltonicity in cubic graphs
• Optimizing concurrency under Scheduling by Edge Reversal
• Optimal multi-TDMA scheduling in ring topology networks
• The complexity of Thomason's algorithm for finding a second Hamiltonian cycle
• Algorithms for long paths in graphs
• Heuristic search for Hamilton cycles in cubic graphs
• Approximability of the upper chromatic number of hypergraphs
• Spanning spiders and light-splitting switches

This page was built for publication: On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs

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