Large Hamiltonian graphs with minimum degree n to the power 1 minus a small epsilon contain a 2-factor consisting of exactly k cycles.
hub
Karp.Reducibility among Combinatorial Problems, pages 85–103
11 Pith papers cite this work, alongside 6,151 external citations. Polarity classification is still indexing.
11
Pith papers citing it
6,151
external citations · Crossref
hub tools
years
2026 11verdicts
UNVERDICTED 11representative citing papers
An algorithm for online Steiner forest achieves constant competitiveness with amortized O(log n) recourse.
MathConstraint generates scalable, automatically verifiable combinatorial problems where LLMs achieve 18.5-66.9% accuracy without tools but roughly double that with solver access.
Random 0/1 polytopes have edge-expansion Θ(d) whp for p ≤ 1-ε and Ω(d^k) for any k when p ≤ 1/2-ε, verifying the Mihail-Vazirani conjecture in strong form with a phase transition at p=1/2.
Exponential lower bounds for cutting planes and Res(⊕) on binary clique formulas for random dense graphs, with polynomial randomized communication complexity for falsified clause finding.
A knowledge-first approach to LLM-driven automatic heuristic design in combinatorial optimization yields better discovery efficiency, transfer, and generalization than code-centric baselines by formalizing a distortion-compression trade-off.
Dynamic programming solves interval ordering in O(2^n poly(n)) time via oracle access to f, in polynomial time when f-f(0) is subadditive or superadditive, with a 2^{n-1} lower bound and NP-hardness for some simple f.
A unified framework yields eight depth measures on matroids with six shown functionally inequivalent, two matching branch-depth and tree-depth, and all coinciding on matroids versus matrices over any field.
O(n^3 log n) algorithm computes maximum (weighted) independent sets for disk graphs with all disks on the convex hull, plus O(n^3 log^2 n) for k-dispersion on the same inputs.
Simulations predict that a virtually connected photonic probabilistic computer solves Erdos-Renyi graph spin-glass ground states orders of magnitude faster than digital annealing units by avoiding embedding and sparsification.
Studying twists of edges in embeddings of cubic graphs yields bounds on the number of singular edges.
citing papers explorer
-
On $2$-factors of Hamiltonian graphs
Large Hamiltonian graphs with minimum degree n to the power 1 minus a small epsilon contain a 2-factor consisting of exactly k cycles.
-
Online Steiner Forest with Recourse
An algorithm for online Steiner forest achieves constant competitiveness with amortized O(log n) recourse.
-
MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMs
MathConstraint generates scalable, automatically verifiable combinatorial problems where LLMs achieve 18.5-66.9% accuracy without tools but roughly double that with solver access.
-
The Mihail-Vazirani conjecture and strong edge-expansion in random $0/1$ polytopes
Random 0/1 polytopes have edge-expansion Θ(d) whp for p ≤ 1-ε and Ω(d^k) for any k when p ≤ 1/2-ε, verifying the Mihail-Vazirani conjecture in strong form with a phase transition at p=1/2.
-
Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
Exponential lower bounds for cutting planes and Res(⊕) on binary clique formulas for random dense graphs, with polynomial randomized communication complexity for falsified clause finding.
-
Back to the Beginning of Heuristic Design: Bridging Code and Knowledge with LLMs
A knowledge-first approach to LLM-driven automatic heuristic design in combinatorial optimization yields better discovery efficiency, transfer, and generalization than code-centric baselines by formalizing a distortion-compression trade-off.
-
Computational Complexity of the Interval Ordering Problem
Dynamic programming solves interval ordering in O(2^n poly(n)) time via oracle access to f, in polynomial time when f-f(0) is subadditive or superadditive, with a 2^{n-1} lower bound and NP-hardness for some simple f.
-
Measuring Depth of Matroids
A unified framework yields eight depth measures on matroids with six shown functionally inequivalent, two matching branch-depth and tree-depth, and all coinciding on matroids versus matrices over any field.
-
Maximum Independent Sets in Disk Graphs with Disks in Convex Position
O(n^3 log n) algorithm computes maximum (weighted) independent sets for disk graphs with all disks on the convex hull, plus O(n^3 log^2 n) for k-dispersion on the same inputs.
-
A virtually connected probabilistic computer as a solver for higher-order, densely connected, or reconfigurable combinatorial optimisation problems
Simulations predict that a virtually connected photonic probabilistic computer solves Erdos-Renyi graph spin-glass ground states orders of magnitude faster than digital annealing units by avoiding embedding and sparsification.
-
Facial diagrams and cycle double cover
Studying twists of edges in embeddings of cubic graphs yields bounds on the number of singular edges.