Published January 1, 2012 | Version v1
Journal article Open

Combinatorial optimization with 2-joins

  • 1. LIP ENS Lyon, CNRS, Lyon, France

Description

A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced sub-graphs, such as perfect graphs and claw-free graphs. In this paper we construct combinatorial polynomial time algorithms for finding a maximum weighted clique, a maximum weighted stable set and an optimal coloring for a class of perfect graphs decomposable by 2-joins: the class of perfect graphs that do not have a balanced skew partition, a 2-join in the complement, nor a homogeneous pair. The techniques we develop are general enough to be easily applied to finding a maximum weighted stable set for another class of graphs known to be decomposable by 2-joins, namely the class of even-hole-free graphs that do not have a star cutset.

Files

bib-a823f75d-fe1a-4aa7-bcb8-768dec363c78.txt

Files (136 Bytes)

Name Size Download all
md5:45b0284f448e18521181e7ae5e8d50c5
136 Bytes Preview Download