Share Your Experience: Take the 2024 Developer Survey

# Tag Info

• 1,318

### Best Hamiltonian Cycle Problem solver

I found myself having to find a Hamilton path in a graph of 200 vertices (what you called "nodes"). My first idea was to use the Hamilton path solver in Maxima ( http://maxima.sourceforge.net/docs/...

### Hamiltonian Cycle as an integer linear programming problem

Here's a simple ILP that nobody has mentioned yet. Given the undirected graph $G=(V, E)$, use binary variables $\pi_{iv}$ for $(i, v)\in [n]\times V$, where $n=|V|$. Variable $\pi_{iv}$ indicates ...
• 10.8k

### Hamiltonian Cycle as an integer linear programming problem

I know this is old, but-- First, make this a 'directed' cycle: only one $e_{ij}$ is true on each vertex, so that $v_i = 1$. This will enable a sort of useful indexing on the cycle. Next, create ...
• 827

### Problems with Unknown Single Exponential Time Agorithms

In a recent paper by Fomin et al. (Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds) it is shown that computing the Hadwiger number of a graph has the complexity ...
• 3,712
Accepted

### Finding a Hamiltonian cycle from perfect matching of a bipartite graph

If $G$ has a disjoint vertex cycle cover then I agree that $H$ must have a perfect matching, but I don't see the other direction (or I have misunderstood how you define $H$ exactly). I think the ...
• 1,429
1 vote

### K-fold Traveling salesman problem - A variant of TSP

There was a paper on the arxive last month, dealing with this generalization of the TSP: The multi-stripe travelling salesman problem Eranda Cela, Vladimir Deineko, Gerhard J. Woeginger (...
• 5,772

Only top scored, non community-wiki answers of a minimum length are eligible