Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Triangle-Free Simple 2-Matchings in Subcubic Graphs (Extended Abstract)
verfasst von : David Hartvigsen, Yanjun Li
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A
simple 2-matching
in an edge-weighted graph is a subgraph all of whose vertices have degree 1 or 2. We consider the problem of finding a maximum weight simple 2-matching that contains no triangles, which is closely related to a class of relaxations of the TSP. Our main results are, for graphs with maximum degree 3, a complete description of the convex hull of incidence vectors of triangle-free simple 2-matchings and a strongly polynomial time algorithm for the above problem. Our system requires the use of a type of comb inequality (introduced by Grötschel and Padberg for the TSP polytope) that has {0,1,2}-coefficients and hence is more general than the well-known blossom inequality used in Edmonds’ characterization of the simple 2-matching polytope.