Decomposing Berge graphs and detecting balanced skew partitions

Nicolas Trotignon ()
Additional contact information
Nicolas Trotignon: Centre d'Economie de la Sorbonne

Cahiers de la Maison des Sciences Economiques from Université Panthéon-Sorbonne (Paris 1)

Abstract: We prove that the problem of deciding whether a graph has a balanced skew partition is NP-hard. We give an O(n9)-time algorithm for the same problem restricted to Berge graphs. Our algorithm is not constructive: it certifies that a graph has a balanced skew partition if it has one. It relies on a new decomposition theorem for Berge graphs, that is more precise than the previously known theorems and implies them easily. Our theorem also implies that every Berge graph can be decomposed in a first step by using only balanced skew partitions, and in a second step by using only 2-joins. Our proof of this new theorem uses at an essential step one of the decomposition theorems of Chudnovsky

Keywords: Perfect graph; Berge graph; 2-join; balanced skew partition; decomposition; detection; recognition (search for similar items in EconPapers)
Pages: 51 pages
Date: 2006-04
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://hal.archives-ouvertes.fr/halshs-00115625 (application/pdf)
https://doi.org/10.1016/j.jctb.2007.07.004

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:mse:wpsorb:b06036

Access Statistics for this paper

More papers in Cahiers de la Maison des Sciences Economiques from Université Panthéon-Sorbonne (Paris 1) Contact information at EDIRC.
Bibliographic data for series maintained by Lucie Label ().