caa a22 4500 475769171 CHVBK 20180406123615.0 cr unu---uuuuu 170329e20000101xx s 000 0 eng 10.1007/s101079900110 doi (NATIONALLICENCE)springer-10.1007/s101079900110 Restricted 2-factor polytopes [Elektronische Daten] [William H. Cunningham, Yaoguang Wang] Abstract. : 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 ≤k≤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. Springer-Verlag Berlin Heidelberg, 2000 Mathematics Subject Classification (1991): Primary 90C27 nationallicence Secondary 05C70 nationallicence Cunningham William H. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, CA aut Wang Yaoguang PeopleSoft Inc., San Mateo, California 94404, US aut https://doi.org/10.1007/s101079900110 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s101079900110 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Cunningham William H. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, CA aut NATIONALLICENCE 700 1- Wang Yaoguang PeopleSoft Inc., San Mateo, California 94404, US aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer