Next: MINIMUM CHORDAL GRAPH COMPLETION
Up: Subgraphs and Supergraphs
Previous: MINIMUM EQUIVALENT DIGRAPH
  Index
- INSTANCE:
Graph
.
- SOLUTION:
An interval graph
that contains G as a subgraph, i.e.,
.
An interval graph is a graph whose vertices can be mapped to distinct intervals
in the real line such that two vertices in the graph have an edge between
them if and only if their corresponding intervals overlap.
- MEASURE:
The cardinality of the interval graph, i.e., |E'|.
- Good News:
Approximable within
[394].
- Garey and Johnson: GT35
Viggo Kann
1999-04-22