Next:
MINIMUM CLIQUE PARTITION
Up:
Covering and Partitioning
Previous:
MAXIMUM H-MATCHING
 
Index
M
INIMUM
B
OTTLENECK
P
ATH
M
ATCHING
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 [
135
].
Viggo Kann
2000-03-20