Combinatorial optimization with 2-joins
From MaRDI portal
Abstract: A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, 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. We also give a simple class of graphs decomposable by 2-joins into bipartite graphs and line graphs, and for which finding a maximum stable set is NP-hard. This shows that having holes all of the same parity gives essential properties for the use of 2-joins in computing stable sets.
Recommendations
- Detecting 2-joins faster
- A generalization of join and an algorithmic recognition problem
- Clique-stable set separation in perfect graphs with no balanced skew-partitions
- Decomposition of even-hole-free graphs with star cutsets and 2-joins
- Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
Cites work
- scientific article; zbMATH DE number 1033812 (Why is no real title available?)
- scientific article; zbMATH DE number 3445275 (Why is no real title available?)
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- A structure theorem for graphs with no cycle with a unique chord and its consequences
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- Balanced \(0,\pm 1\) matrices. I: Decomposition
- Berge trigraphs
- Bull-free Berge graphs are perfect
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Compositions for perfect graphs
- Decomposing Berge graphs and detecting balanced skew partitions
- Decomposition of balanced matrices
- Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
- Decomposition of regular matroids
- Detecting 2-joins faster
- Even-hole-free graphs part II: Recognition algorithm
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Even-hole-free graphs. I: Decomposition theorem
- Geometric algorithms and combinatorial optimization
- Graph minor theory
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XX: Wagner's conjecture
- Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes
- On diameters and radii of bridged graphs
- Optimizing Bull-Free Perfect Graphs
- Paths, Trees, and Flowers
- Recognizing Berge graphs
- Square-free perfect graphs.
- Star-cutsets and perfect graphs
- The ellipsoid method and its consequences in combinatorial optimization
- The strong perfect graph theorem
- Triangulated neighborhoods in even-hole-free graphs
- Weakly triangulated graphs
Cited in
(17)- On the linear extension complexity of stable set polytopes for perfect graphs
- Linear balanceable and subcubic balanceable graphs
- One-three join: a graph operation and its consequences
- Minimum weighted clique cover on claw‐free perfect graphs
- Detecting 2-joins faster
- Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
- A faster algorithm to recognize even-hole-free graphs
- The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
- Coloring perfect graphs with no balanced skew-partitions
- Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs
- Perfect graphs with no balanced skew-partition are 2-clique-colorable
- A faster algorithm to recognize even-hole-free graphs
- The (theta, wheel)-free graphs. IV: Induced paths and cycles
- Computing \(H\)-joins with application to 2-modular decomposition
- Clique-stable set separation in perfect graphs with no balanced skew-partitions
- A generalization of join and an algorithmic recognition problem
- 3-colouring AT-free graphs in polynomial time
This page was built for publication: Combinatorial optimization with 2-joins
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765197)
