Next: MINIMUM CLIQUE PARTITION
Up: Covering and Partitioning
Previous: MAXIMUM H-MATCHING
  Index
- INSTANCE:
Graph
with an even number of vertices, and a weight
function
.
- SOLUTION:
A disjoint path perfect matching for G, i.e., a collection
of disjoint simple paths in G with disjoint
end points.
- MEASURE:
Weight of the heaviest path in the matching, i.e.,
.
- Good News:
Approximable within 2 [125].
Viggo Kann
1999-04-22