A Polynomial-Time Algorithm to Determine (Almost) Hamiltonicity of Dense Regular Graphs
From MaRDI portal
Publication:5084096
DOI10.1137/20M1356191zbMath1491.05120arXiv2007.14502OpenAlexW3045552448MaRDI QIDQ5084096
Publication date: 23 June 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.14502
Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Density (toughness, etc.) (05C42)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
- Eigenvalues and expanders
- Dominating cycles in regular 3-connected graphs
- Hamilton cycles in regular 2-connected graphs
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- On the approximation hardness of dense TSP and other path problems
- Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
- Hamilton decompositions of regular expanders: applications
- The robust component structure of dense regular graphs and applications
- Finding Hamilton cycles in robustly expanding digraphs
- A proof of Sumner's universal tournament conjecture for large tournaments
- Minimizing the Number of Triangular Edges
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Max Cut and the Smallest Eigenvalue
- Proof of the 1-factorization and Hamilton Decomposition Conjectures
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Some Theorems on Abstract Graphs
This page was built for publication: A Polynomial-Time Algorithm to Determine (Almost) Hamiltonicity of Dense Regular Graphs
