Combinatorial optimization with 2-joins

DOI10.1016/j.jctb.2011.06.002zbMath1235.90132arXiv1309.1547OpenAlexW1971558924WikidataQ59902615 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

zbMATH Keywords

decompositioncombinatorial optimizationperfect graphscoloringmaximum cliquestructure2-joineven-hole-free graphsberge graphsminimum stable set

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (13)

Detecting 2-joins faster ⋮ Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree ⋮ The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring ⋮ Minimum weighted clique cover on claw‐free perfect graphs ⋮ 3-colouring AT-free graphs in polynomial time ⋮ Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs ⋮ The (theta, wheel)-free graphs. IV: Induced paths and cycles ⋮ Coloring perfect graphs with no balanced skew-partitions ⋮ Perfect Graphs with No Balanced Skew-Partition are 2-Clique-Colorable ⋮ On the linear extension complexity of stable set polytopes for perfect graphs ⋮ Unnamed Item ⋮ A faster algorithm to recognize even-hole-free graphs ⋮ 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

This page was built for publication: Combinatorial optimization with 2-joins