Detecting 2-joins faster
From MaRDI portal
Publication:2376790
DOI10.1016/j.jda.2012.11.003zbMath1266.05163arXiv1107.3977WikidataQ59902211 ScholiaQ59902211MaRDI QIDQ2376790
Kristina Vušković, Nicolas Trotignon, Pierre Charbit, Michel A. Habib
Publication date: 24 June 2013
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1107.3977
induced subgraphs; perfect graphs; detection; 2-join; balanced bipartite graphs; even-hole-free graphs; claw free graphs; edge cutset; closed classes of graphs
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, Colouring perfect graphs with bounded clique number, Computing \(H\)-joins with application to 2-modular decomposition, Coloring perfect graphs with no balanced skew-partitions, Combinatorial optimization with 2-joins, The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs, The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring, The (theta, wheel)-free graphs. IV: Induced paths and cycles, A faster algorithm to recognize even-hole-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Combinatorial optimization with 2-joins
- The strong perfect graph theorem
- 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
- Balanced \(0,\pm 1\) matrices. II: Recognition algorithm
- Compositions for perfect graphs
- Decomposing Berge graphs and detecting balanced skew partitions
- Recognizing Berge graphs
- Even-hole-free graphs part I: Decomposition theorem
- Linear Time Split Decomposition Revisited
- Even-hole-free graphs part II: Recognition algorithm
- A Combinatorial Decomposition Theory
- An O(n2) Algorithm for Undirected Split Decomposition
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- Berge trigraphs
