A survey of the algorithmic aspects of modular decomposition

M Habib, C Paul - Computer Science Review, 2010 - Elsevier
Modular decomposition is a technique that applies to (but is not restricted to) graphs. The
notion of a module naturally appears in the proofs of many graph theoretical theorems …

Modular decomposition and transitive orientation

RM McConnell, JP Spinrad - Discrete Mathematics, 1999 - Elsevier
A module of an undirected graph is a set X of nodes such for each node x not in X, either
every member of X is adjacent to x, or no member of X is adjacent to x. There is a canonical …

Substitution decomposition for discrete structures and connections with combinatorial optimization

RH Möhring, FJ Radermacher - North-Holland mathematics studies, 1984 - Elsevier
In this paper we deal with the substitution decomposition as known for Boolean functions,
set systems and relations. It is shown how combinatorial optimization problems, particularly …

A new linear algorithm for modular decomposition

A Cournier, M Habib - Trees in Algebra and Programming—CAAP'94: 19th …, 1994 - Springer
We present here a new algorithm linear in time and space complexity for Modular
Decomposition. This algorithm relies on structural properties of prime graphs (see theorems …

Simpler linear-time modular decomposition via recursive factorizing permutations

M Tedder, D Corneil, M Habib, C Paul - … 2008, Reykjavik, Iceland, July 7-11 …, 2008 - Springer
Modular decomposition is fundamental for many important problems in algorithmic graph
theory including transitive orientation, the recognition of several classes of graphs, and …

[图书][B] Theory Of 2-structures, The: A Framework For Decomposition And Transformation Of Graphs

A Ehrenfeucht, T Harju, G Rozenberg - 1999 - books.google.com
The theory of 2-structures provides a convenient framework for decomposition and
transformation of mathematical systems where one or several different binary relationships …

P4-trees and substitution decomposition

J Spinrad - Discrete applied mathematics, 1992 - Elsevier
Pa-trees and substitution decomposition* Page 1 Discrete Applied Mathematics 39 ( 199;)
263-291 North-Holland 263 Pa-trees and substitution decomposition* Jeremy Spinrad …

Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and boolean functions

RH Möhring - Annals of Operations Research, 1985 - Springer
In the last years, decomposition techniques have seen an increasing application to the
solution of problems from operations research and combinatorial optimization, in particular …

On the enumeration of minimal dominating sets and related notions

MM Kanté, V Limouzy, A Mary, L Nourine - SIAM Journal on Discrete …, 2014 - SIAM
A dominating set D in a graph is a subset of its vertex set such that each vertex is either in D
or has a neighbor in D. In this paper, we are interested in the enumeration of (inclusionwise) …

[HTML][HTML] Linear-time modular decomposition of directed graphs

RM McConnell, F De Montgolfier - Discrete Applied Mathematics, 2005 - Elsevier
Modular decomposition of graphs is a powerful tool with many applications in graph theory
and optimization. There are efficient linear-time algorithms that compute the decomposition …