A matching problem with side conditions |
| |
Authors: | Gérard Cornuéjols William Pulleyblank |
| |
Institution: | Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA 15213, USA;Department of Computer Science, The University of Calgary, Calgary, Alberta T2N 1N4, Canada |
| |
Abstract: | Given a graph G, a 2-matching is an assignment of nonnegative integers to the edges of G such that for each node i of G, the sum of the values on the edges incident with i is at most 2. A triangle-free 2-matching is a 2-matching such that no cycle of size 3 in G has the value 1 assigned to all of its edges. In this paper we describe explicity the convex hull of triangle-free 2-matchings by means of its extreme points and of its facets. We give a polynomially bounded algorithm which maximizes a linear function over the set of triangle-free 2-matchings. Finally we discuss some related problems. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|