Next: MAXIMUM TRIANGLE PACKING
Up: Covering and Partitioning
Previous: MINIMUM FEEDBACK ARC SET
  Index
- INSTANCE:
Graph
.
- SOLUTION:
A maximal matching E', i.e., a subset
such that
no two edges in E' shares a common endpoint and every edge in
E-E' shares a common endpoint with some edge in E'.
- MEASURE:
Cardinality of the matching, i.e., |E'|.
- Good News:
Approximable within 2 (any maximal matching).
- Bad News:
APX-complete [448].
- Comment:
Transformation from MINIMUM VERTEX COVER.
- Garey and Johnson: GT10
Viggo Kann
1999-04-22