Algorithmic aspects of a general modular decomposition theory

DOI10.1016/j.dam.2008.11.001zbMath1190.68029OpenAlexW2952739563MaRDI QIDQ1026102

J. Blot

Publication date: 24 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.11.001

zbMATH Keywords

modular decompositionhomogeneous relationintersecting submodular function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (3)

Meta-kernelization with structural parameters ⋮ \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs ⋮ A survey of the algorithmic aspects of modular decomposition

Cites Work

• Theory of 2-structures. II: Representation through labeled tree families
• Complement reducible graphs
• Partitive hypergraphs
• A tree representation for \(P_ 4\)-sparse graphs
• Submodular functions and optimization
• The complexity of comparability graph recognition and coloring
• Modular decomposition and transitive orientation
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Linear-time modular decomposition of directed graphs
• Fast algorithms to enumerate all common intervals of two permutations
• The complexity of modular decomposition of Boolean functions
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• Three Partition Refinement Algorithms
• Graph Classes: A Survey
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
• Algorithm Theory - SWAT 2004
• Algorithms – ESA 2005
• Transitiv orientierbare Graphen
• Algorithms and Computation
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algorithmic aspects of a general modular decomposition theory