Decomposing Berge graphs and detecting balanced skew partitions (Q2464161)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decomposing Berge graphs and detecting balanced skew partitions |
scientific article |
Statements
Decomposing Berge graphs and detecting balanced skew partitions (English)
0 references
10 December 2007
0 references
A hole in a graph is an induced cycle of order at least 4. A Berge graph has no odd holes in either itself or its complement. The author shows that the problem of deciding whether a graph has a balanced skew partition is NP-hard, but gives an \(O(n^9)\)-time algorithm for the same problem restricted to Berge graphs. The algorithm is not constructive; it only certifies whether a graph has a balanced skew partition or not. It relies on a new decomposition theorem for Berge graphs, which also implies that every Berge graph can be decomposed first by using only balanced skew partitions and then by using only 2-joins.
0 references
perfect graph
0 references
Berge graph
0 references
2-join
0 references
balanced skew partition
0 references
decomposition
0 references
detection
0 references
recognition
0 references