Detecting 2-joins faster

DOI10.1016/J.JDA.2012.11.003zbMATH Open1266.05163arXiv1107.3977OpenAlexW2061452048WikidataQ59902211 ScholiaQ59902211MaRDI QIDQ2376790FDOQ2376790

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)

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.

Full work available at URL: https://arxiv.org/abs/1107.3977

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

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)

Cites Work

• Decomposing Berge graphs and detecting balanced skew partitions
• Berge trigraphs
• The strong perfect graph theorem
• Recognizing Berge graphs
• The structure of claw-free graphs
• A Combinatorial Decomposition Theory
• Compositions for perfect graphs
• Linear time split decomposition revisited
• Decomposition of balanced matrices
• Square-free perfect graphs.
• Title not available (Why is that?)
• An O(n2) Algorithm for Undirected Split Decomposition
• Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
• Even-hole-free graphs. I: Decomposition theorem
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Even-hole-free graphs part II: Recognition algorithm
• Balanced \(0,\pm 1\) matrices. I: Decomposition
• Combinatorial optimization with 2-joins
• Balanced \(0,\pm 1\) matrices. II: Recognition algorithm

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
• The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• Computing \(H\)-joins with application to 2-modular decomposition
• 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)