Next: MAXIMUM H-MATCHING
Up: Covering and Partitioning
Previous: MINIMUM MAXIMAL MATCHING
  Index
- INSTANCE:
Graph
.
- SOLUTION:
A triangle packing for G, i.e., a collection
of
disjoint subsets of V, each containing exactly 3 vertices, such that
for each
Vi={ui,vi,wi},
,
all three of the edges
,
,
and
belong to E.
- MEASURE:
Cardinality of the triangle packing, i.e., the number of disjoint subsets
Vi.
- Good News:
Approximable within 3/2
for any
[250].
- Bad News:
APX-complete [265].
- Comment:
Transformation from bounded MAXIMUM 3-DIMENSIONAL
MATCHING.
Admits a PTAS for planar graphs [50]
and for
-precision unit disk graphs [249].
Still APX-complete when the degree of G is bounded by 4 [265].
- Garey and Johnson: GT11
Viggo Kann
1999-04-22