Modular decomposition and transitive orientation
type: Item
instance of: scholarly article
title: Modular decomposition and transitive orientation
zbMATH Open document ID: 0933.05146
DOI: 10.1016/S0012-365X(98)00319-7
author: R. M. McConnell
author: Jeremy P. Spinrad
published in: Discrete Mathematics
publication date: 2000-04-04T00:00:00Z
review text: A module of a graph \(G\) is a set \(X\) of vertices such that, for every \(x\in V(G)-X\), either \(x\) is adjacent to every element of \(X\) or \(x\) is adjacent to no vertex in \(X\). The modular decomposition of \(G\) is an \(O(n)\)-space representation of the modules of \(G\). The authors introduce linear time algorithms to construct the modular decomposition of a graph and a transitive orientation of a comparability graph. Note that a linear time algorithm for the modular decompositions of both directed and undirected graphs was suggested by \textit{A. Cournier} and \textit{M. Habib} [Lect. Notes Comput. Sci. 657, 212-224 (1993)].
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1334546
zbMATH Keywords: module
zbMATH Keywords: modular decomposition
zbMATH Keywords: transitive orientation
zbMATH Keywords: comparability graph
zbMATH Keywords: linear time algorithm
Wikidata QID: Q57535770
reviewed by: G. Gutin
MaRDI profile type: Publication
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: A Fast Algorithm for the Decomposition of Graphs and Posets
cites work: Partitive hypergraphs
cites work: On testing isomorphism of permutation graphs
cites work: Complement reducible graphs
cites work: A Linear Recognition Algorithm for Cographs
cites work: Q4281647
cites work: Q4954442
cites work: Partially Ordered Sets
cites work: An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
cites work: Primitivity is hereditary for 2-structures
cites work: Theory of 2-structures. I: Clans, basic subclasses, and morphisms
cites work: Theory of 2-structures. II: Representation through labeled tree families
cites work: A linear-time algorithm for a special case of disjoint set union
cites work: Transitiv orientierbare Graphen
cites work: The complexity of comparability graph recognition and coloring
cites work: Q3328583
cites work: Q3291037
cites work: On the X-join decomposition for undirected graphs
cites work: Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
cites work: An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
cites work: Q3128916
cites work: Q3686754
cites work: Incremental modular decomposition
cites work: Transitive Orientation of Graphs and Identification of Permutation Graphs
cites work: Circular permutation graphs
cites work: Q3670598
cites work: On Comparability and Permutation Graphs
cites work: \(P_ 4\)-trees and substitution decomposition
cites work: A linear time algorithm to recognize circular permutation graphs
cites work: Single Machine Scheduling with Series-Parallel Precedence Constraints
cites work: The Recognition of Series Parallel Digraphs
Recommended article: The orientation of modules based on graph decomposition
Recommended article: A characterization of modularity and orthomodularity
Recommended article: Q5851973
Recommended article: Modular decomposition of the Orlik-Terao algebra
Recommended article: Q4519451
Recommended article: Modular decomposition and the reconstruction conjecture
Recommended article: Decomposing torsion modules
Recommended article: Direct decompositions of orthomodular lattices
Recommended article: LATTICE DECOMPOSITION OF MODULES
description: scientific article; zbMATH DE number 1334546