max planck institut
informatik
informatik
MPI-I-97-1-006. February 1997, 30 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry
Abstract in LaTeX format:
The optimal $k$-restricted 2-factor problem consists of finding,
in a complete undirected graph $K_n$, a minimum cost 2-factor
(subgraph having degree 2 at every node) with all components having more
than $k$ nodes.
The problem is a relaxation of the well-known symmetric travelling
salesman problem, and is equivalent to it when $\frac{n}{2}\leq k\leq n-1$.
We study the $k$-restricted 2-factor polytope. We present a large
class of valid inequalities, called bipartition
inequalities, and describe some of their properties; some of
these results are new even for the travelling salesman polytope.
For the case $k=3$, the triangle-free 2-factor polytope,
we derive a necessary and sufficient condition for such inequalities
to be facet inducing.
Acknowledgement:
References to related material:
| To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |
|---|---|
| 325 KBytes | |
| Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView | |
BibTeX