Detecting 2-joins faster

DOI10.1016/J.JDA.2012.11.003MaRDI QIDQ2376790zbMATH OpenOpenAlexWikidataFDO

Authors Nicolas Trotignon, Kristina Vušković, Pierre Charbit, M. 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

zbMATH Keywords

2-joininduced subgraphsperfect graphsdetectionbalanced bipartite graphseven-hole-free graphsclaw free graphsedge cutsetclosed classes of graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 2-joins are edge cutsets that naturally appear in the decomposition of several classes of graphs closed under taking induced subgraphs, such as balanced bipartite graphs, even-hole-free graphs, perfect graphs and claw-free graphs. Their detection is needed in several algorithms, and is the slowest step for some of them. The classical method to detect a 2-join takes $O(n^{3}m)$ time where $n$ is the number of vertices of the input graph and $m$ the number of its edges. To detect emph{non-path} 2-joins (special kinds of 2-joins that are needed in all of the known algorithms that use 2-joins), the fastest known method takes time $O(n^{4}m)$. Here, we give an $O(n^{2}m)$-time algorithm for both of these problems. A consequence is a speed up of several known algorithms.

Recommendations

• Combinatorial optimization with 2-joins
• Computing \(H\)-joins with application to 2-modular decomposition
• Algorithms for some \(H\)-join decompositions
• A generalization of join and an algorithmic recognition problem
• Decomposition of even-hole-free graphs with star cutsets and 2-joins

Cites work

• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• A Combinatorial Decomposition Theory
• An O(n2) Algorithm for Undirected Split Decomposition
• Balanced \(0,\pm 1\) matrices. I: Decomposition
• Balanced \(0,\pm 1\) matrices. II: Recognition algorithm
• Berge trigraphs
• Combinatorial optimization with 2-joins
• 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
• Even-hole-free graphs part II: Recognition algorithm
• Even-hole-free graphs. I: Decomposition theorem
• Linear time split decomposition revisited
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Recognizing Berge graphs
• Square-free perfect graphs.
• The strong perfect graph theorem
• The structure of claw-free graphs

Cited in

(10)

• A generalization of join and an algorithmic recognition problem
• Coloring perfect graphs with no balanced skew-partitions
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• A faster algorithm to recognize even-hole-free graphs
• Colouring perfect graphs with bounded clique number
• Computing \(H\)-joins with application to 2-modular decomposition
• The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• Combinatorial optimization with 2-joins
• A faster algorithm to recognize even-hole-free graphs

This page was built for publication: Detecting 2-joins faster

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2376790)