MINIMUM BOTTLENECK PATH MATCHING

Next: MINIMUM CLIQUE PARTITION Up: Covering and Partitioning Previous: MAXIMUM H-MATCHING Index

INSTANCE: Graph $G=\left(V,E\right)$ with an even number of vertices, and a weight function $w : E \rightarrow N$ .
SOLUTION: A disjoint path perfect matching for G, i.e., a collection $P_1,P_2,\ldots,P_{\vert V\vert/2}$ of disjoint simple paths in G with disjoint end points.
MEASURE: Weight of the heaviest path in the matching, i.e., $\max\limits_{1\le i\le \vert V\vert/2}\sum\limits_{e\in P_i} w(e)$ .
Good News: Approximable within 2 [135].

Viggo Kann
2000-03-20