Next:
GT13 MINIMUM CLIQUE
Up:
Covering and Partitioning
Previous:
GT11 MAXIMUM H-MATCHING
-
I
NSTANCE
:
Graph
with an even number of vertices, and a weight
function
.
-
S
OLUTION
:
A disjoint path perfect matching for
G
, i.e., a collection
of disjoint simple paths in
G
with disjoint
end points.
-
M
EASURE
:
Weight of the heaviest path in the matching, i.e.,
.
-
Good News:
Approximable within 2 [
92
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997