(, )-Modules in Graphs
From MaRDI portal
Publication:6188517
Abstract: Modular Decomposition focuses on repeatedly identifying a module M (a collection of vertices that shares exactly the same neighbourhood outside of M) and collapsing it into a single vertex. This notion of exactitude of neighbourhood is very strict, especially when dealing with real world graphs. We study new ways to relax this exactitude condition. However, generalizing modular decomposition is far from obvious. Most of the previous proposals lose algebraic properties of modules and thus most of the nice algorithmic consequences. We introduce the notion of an ({alpha}, {�eta})-module, a relaxation that allows a bounded number of errors in each node and maintains some of the algebraic structure. It leads to a new combinatorial decomposition with interesting properties. Among the main results in this work, we show that minimal ({alpha}, {�eta})-modules can be computed in polynomial time, and that every graph admits an ({alpha},{�eta})-modular decomposition tree, thus generalizing Gallai's Theorem (which corresponds to the case for {alpha} = {�eta} = 0). Unfortunately we give evidence that computing such a decomposition tree can be difficult.
Recommendations
Cites work
- A k-structure generalization of the theory of 2-structures
- A Combinatorial Decomposition Theory
- A complete complexity classification of the role assignment problem
- A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs
- A survey of the algorithmic aspects of modular decomposition
- Algorithmic aspects of a general modular decomposition theory
- Algorithms solving the matching cut problem
- Almost all comparability graphs are UPO
- Approximating modular decomposition is hard
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Complement reducible graphs
- Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
- Decomposition of perfect graphs
- Drawing graphs using modular decomposition
- Forbidden subgraph decomposition
- scientific article; zbMATH DE number 3906240 (Why is no real title available?)
- scientific article; zbMATH DE number 1202982 (Why is no real title available?)
- scientific article; zbMATH DE number 2044946 (Why is no real title available?)
- Matching cutsets in graphs
- Matching cutsets in graphs of diameter 2
- On a property of the class of n-colorable graphs
- ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
- On sets of integers containing k elements in arithmetic progression
- On the Erdős-Hajnal conjecture for six-vertex tournaments
- Partition refinement techniques: an interesting algorithmic tool kit
- Partitive hypergraphs
- Ramsey-type theorems
- Recognizing decomposable graphs
- Recognizing median graphs in subquadratic time
- Submodular functions and optimization
- The complexity of the matching-cut problem for planar graphs and other graph classes
- The structure of median graphs
- Theory of 2-structures
- Theory of 2-structures. II: Representation through labeled tree families
- Transitiv orientierbare Graphen
- Tree-representation of set families and applications to combinatorial decompositions
- Twin-width. I: Tractable FO model checking
Cited in
(3)
This page was built for publication: \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6188517)
