Computing H-joins with application to 2-modular decomposition

DOI10.1007/S00453-013-9820-1MaRDI QIDQ486993zbMATH OpenOpenAlexFDO

Authors Antoine Mamcarz, Fabien De Montgolfier, M. A. Habib

Publication date 19 January 2015

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-013-9820-1

zbMATH Keywords

graph decompositions\(H\)-joinhomogeneous pairs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Algorithms for some \(H\)-join decompositions
• Detecting 2-joins faster
• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• Combinatorial optimization with 2-joins
• Graph-Theoretic Concepts in Computer Science

Cites work

• A Combinatorial Decomposition Theory
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A survey of the algorithmic aspects of modular decomposition
• Algorithms for some \(H\)-join decompositions
• An algorithm for finding homogeneous pairs
• Balanced \(0,\pm 1\) matrices. I: Decomposition
• Boolean-width of graphs
• Bull-free Berge graphs are perfect
• Detecting 2-joins faster
• Linear time split decomposition revisited
• List Partitions
• Partition refinement techniques: an interesting algorithmic tool kit
• Partitive hypergraphs
• Three Partition Refinement Algorithms
• Two algorithms for general list matrix partitions
• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth

Cited in

(2)

• Detecting 2-joins faster
• Algorithms for some \(H\)-join decompositions

This page was built for publication: Computing \(H\)-joins with application to 2-modular decomposition

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