Computing H-joins with application to 2-modular decomposition

DOI10.1007/S00453-013-9820-1zbMATH Open1306.05235OpenAlexW2068211971MaRDI QIDQ486993FDOQ486993

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

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

zbMATH Keywords

graph decompositions\(H\)-joinhomogeneous pairs

Mathematics Subject Classification ID

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

Cites Work

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

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)