\(P_ 4\)-trees and substitution decomposition

DOI10.1016/0166-218X(92)90180-IzbMath0758.68036MaRDI QIDQ1201812

Jeremy P. Spinrad

Publication date: 17 January 1993

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

zbMATH Keywords

cographsmodular decompositioncotreessubstitution decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (49)

The graph sandwich problem for 1-join composition is NP-complete ⋮ A \(k\)-structure generalization of the theory of 2-structures ⋮ The homogeneous set sandwich problem ⋮ Note on the homogeneous set sandwich problem ⋮ A linear algorithm to decompose inheritance graphs into modules ⋮ Tournaments with maximal decomposability ⋮ \(P_{4}\)-laden graphs: A new class of brittle graphs ⋮ An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures ⋮ On semi-\(P_ 4\)-sparse graphs ⋮ The \(\{-2,-1\}\)-selfdual and decomposable tournaments ⋮ Unnamed Item ⋮ Decomposability and co-modular indices of tournaments ⋮ Decomposability index of tournaments ⋮ Minimal indecomposable graphs ⋮ On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs ⋮ 3-minimal triangle-free graphs ⋮ Unnamed Item ⋮ Decomposition tree of a lexicographic product of binary structures ⋮ Birecognition of prime graphs, and minimal prime graphs ⋮ Efficient parallel modular decomposition (extended abstract) ⋮ Primality, criticality and minimality problems in trees ⋮ Indecomposability graph and indecomposability recognition ⋮ The \(C_{3}\)-structure of the tournaments. ⋮ Recognition of prime graphs from a prime subgraph ⋮ Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs ⋮ Transitive closure for restricted classes of partial orders ⋮ Prime orientable graphs ⋮ An algorithm for finding homogeneous pairs ⋮ On the structure of bull-free perfect graphs ⋮ Finite orders which are reconstructible up to duality by their comparability graphs ⋮ Cut-primitive directed graphs versus clan-primitive directed graphs ⋮ Linear-time modular decomposition of directed graphs ⋮ Triangle-free graphs which are minimal for some nonstable 4-vertex subset ⋮ Critically indecomposable graphs ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ Convex circuit-free coloration of an oriented graph ⋮ Making a tournament indecomposable by one subtournament-reversal operation ⋮ Editing to prime graphs ⋮ Prime 3-uniform hypergraphs ⋮ The recognition of the class of indecomposable digraphs under low hemimorphy ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The closure of monadic NP ⋮ Indecomposability graph and critical vertices of an indecomposable graph ⋮ Modular decomposition and transitive orientation ⋮ Two {4,n-3}-isomorphic n-vertex digraphs are hereditarily isomorphic ⋮ Some Algorithms on Conditionally Critical Indecomposable Graphs ⋮ Critical 3-hypergraphs ⋮ An efficient algorithm for solving the homogeneous set sandwich problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On finding the jump number of a partial order by substitution decomposition
• Graph derivatives
• On the X-join decomposition for undirected graphs
• Complement reducible graphs
• Partitive hypergraphs
• Comparability graphs and a new matroid
• Graphs indecomposable with respect to the X-join
• Partially ordered sets and their comparability graphs
• A Fast Algorithm for the Decomposition of Graphs and Posets
• On Comparability and Permutation Graphs
• A Linear Recognition Algorithm for Cographs
• Optimal Sequencing by Modular Decomposition: Polynomial Algorithms
• Incremental modular decomposition
• On testing isomorphism of permutation graphs
• Single Machine Scheduling with Series-Parallel Precedence Constraints
• Decomposition of Directed Graphs
• Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
• Efficiency of a Good But Not Linear Set Union Algorithm
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Transitiv orientierbare Graphen

This page was built for publication: \(P_ 4\)-trees and substitution decomposition