Combinatorial optimization with 2-joins
From MaRDI portal
Publication:765197
DOI10.1016/J.JCTB.2011.06.002zbMATH Open1235.90132DBLPjournals/jct/TrotignonV12arXiv1309.1547OpenAlexW1971558924WikidataQ59902615 ScholiaQ59902615MaRDI QIDQ765197FDOQ765197
Kristina Vušković, Nicolas Trotignon
Publication date: 19 March 2012
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1309.1547
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
combinatorial optimizationdecompositionmaximum clique2-joincoloringstructureperfect graphseven-hole-free graphsberge graphsminimum stable set
Cites Work
- Decomposition of regular matroids
- Geometric algorithms and combinatorial optimization
- Paths, Trees, and Flowers
- Graph minors. XX: Wagner's conjecture
- The ellipsoid method and its consequences in combinatorial optimization
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Graph minors. XIII: The disjoint paths problem
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Decomposing Berge graphs and detecting balanced skew partitions
- Berge trigraphs
- The strong perfect graph theorem
- Recognizing Berge graphs
- Graph minor theory
- Weakly triangulated graphs
- Title not available (Why is that?)
- On diameters and radii of bridged graphs
- Compositions for perfect graphs
- Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes
- Decomposition of balanced matrices
- Square-free perfect graphs.
- A structure theorem for graphs with no cycle with a unique chord and its consequences
- Star-cutsets and perfect graphs
- Detecting 2-joins faster
- Optimizing Bull-Free Perfect Graphs
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- Bull-free Berge graphs are perfect
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
- Even-hole-free graphs. I: Decomposition theorem
- Even-hole-free graphs part II: Recognition algorithm
- Balanced \(0,\pm 1\) matrices. I: Decomposition
- Title not available (Why is that?)
- Triangulated neighborhoods in even-hole-free graphs
Cited In (13)
- Linear balanceable and subcubic balanceable graphs
- Detecting 2-joins faster
- Coloring perfect graphs with no balanced skew-partitions
- 3-colouring AT-free graphs in polynomial time
- Perfect graphs with no balanced skew-partition are 2-clique-colorable
- Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
- The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
- The (theta, wheel)-free graphs. IV: Induced paths and cycles
- Minimum weighted clique cover on claw‐free perfect graphs
- On the linear extension complexity of stable set polytopes for perfect graphs
- A faster algorithm to recognize even-hole-free graphs
- Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs
- Title not available (Why is that?)
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)
