Combinatorial optimization with 2-joins
From MaRDI portal
Publication:765197
DOI10.1016/j.jctb.2011.06.002zbMath1235.90132arXiv1309.1547WikidataQ59902615 ScholiaQ59902615MaRDI QIDQ765197
Kristina Vušković, Nicolas Trotignon
Publication date: 19 March 2012
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1309.1547
decomposition; combinatorial optimization; perfect graphs; coloring; maximum clique; structure; 2-join; even-hole-free graphs; berge graphs; minimum stable set
90C27: Combinatorial optimization
Related Items
Unnamed Item, Minimum weighted clique cover on claw‐free perfect graphs, Coloring perfect graphs with no balanced skew-partitions, Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs, 3-colouring AT-free graphs in polynomial time, 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, On the linear extension complexity of stable set polytopes for perfect graphs, A faster algorithm to recognize even-hole-free graphs, Detecting 2-joins faster, Perfect Graphs with No Balanced Skew-Partition are 2-Clique-Colorable, Linear Balanceable and Subcubic Balanceable Graphs*
Cites Work
- Unnamed Item
- Unnamed Item
- Graph minors. XX: Wagner's conjecture
- Weakly triangulated graphs
- The strong perfect graph theorem
- Triangulated neighborhoods in even-hole-free graphs
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Bull-free Berge graphs are perfect
- On diameters and radii of bridged graphs
- Star-cutsets and perfect graphs
- Decomposition of regular matroids
- The ellipsoid method and its consequences in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- Square-free perfect graphs.
- Decomposition of balanced matrices
- Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
- Balanced \(0,\pm 1\) matrices. I: Decomposition
- 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
- Compositions for perfect graphs
- Detecting 2-joins faster
- Decomposing Berge graphs and detecting balanced skew partitions
- Recognizing Berge graphs
- Even-hole-free graphs part I: Decomposition theorem
- Even-hole-free graphs part II: Recognition algorithm
- Graph minor theory
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- Optimizing Bull-Free Perfect Graphs
- Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes
- A structure theorem for graphs with no cycle with a unique chord and its consequences
- Paths, Trees, and Flowers
- Berge trigraphs
