Approximate and randomized algorithms for computing a second Hamiltonian cycle

DOI10.1007/S00453-024-01238-ZMaRDI QIDQ6614106

Victor Zamaraev, George B. Mertzios, Paul G. Spirakis, Argyrios Deligkas

Publication date: 7 October 2024

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmrandomized algorithmHamiltonian cyclegraph with minimum degree 3

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure
• A degree constraint for uniquely Hamiltonian graphs
• Spanning cycles of nearly cubic graphs
• On the complexity of the parity argument and other inefficient proofs of existence
• Independent dominating sets and a second hamiltonian cycle in regular graphs
• Chords of longest cycles in cubic graphs
• Vertices of small degree in uniquely Hamiltonian graphs
• Long cycles in Hamiltonian graphs
• A new upper bound for the traveling salesman problem in cubic graphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Uniquely Hamiltonian Graphs of Minimum Degree 4
• The traveling salesman problem in bounded degree graphs
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• Independent dominating sets and hamiltonian cycles
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• The Traveling Salesman Problem for Cubic Graphs
• Determinant Sums for Undirected Hamiltonicity
• On Hamiltonian Circuits
• Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs

This page was built for publication: Approximate and randomized algorithms for computing a second Hamiltonian cycle

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