Decomposition of Directed Graphs
From MaRDI portal
Publication:3960725
DOI10.1137/0603021zbMath0497.05031MaRDI QIDQ3960725
Publication date: 1982
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0603021
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C20: Directed graphs (digraphs), tournaments
Related Items
Dynamic Distance Hereditary Graphs Using Split Decomposition, A Representation Theorem for Union-Difference Families and Application, Graphs with bounded induced distance, Domination graphs: Examples and counterexamples, Recognizing locally equivalent graphs, Decomposition of k-ary relations, Networks with small stretch number, Decomposition of partial orders, Circle graphs and monadic second-order logic, Solving some NP-complete problems using split decomposition, Clique-width of graphs defined by one-vertex extensions, Decomposition of submodular functions, A decomposition of distributive lattices, An algorithm for minimizing setups in precedence constrained scheduling, On finding the jump number of a partial order by substitution decomposition, N-free posets as generalizations of series-parallel posets, Isotropic systems, On submodular function minimization, Graphic presentations of isotropic systems, Reducing prime graphs and recognizing circle graphs, \(P_ 4\)-comparability graphs, Representations of graphs and networks (coding, layouts and embeddings), \(P_ 4\)-trees and substitution decomposition, Minimally 3-connected isotropic systems, Efficient parallel recognition algorithms of cographs and distance hereditary graphs, Connectivity and \(\beta\)-invariants of isotropic systems and 4-regular graphs, On the closure of graphs under substitution, PC trees and circular-ones arrangements., MAD trees and distance-hereditary graphs, Distance labeling scheme and split decomposition, The graph sandwich problem for 1-join composition is NP-complete, Basic perfect graphs and their extensions, An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures, Compositions for perfect graphs, Mutant knots and intersection graphs, The modular decomposition of countable graphs. Definition and construction in monadic second-order logic, Recognizability, hypergraph operations, and logical types, A contract-based model for directed network formation, Graph decompositions definable in monadic second-order logic, The bi-join decomposition, Digraph Decompositions and Eulerian Systems
Cites Work
- Unnamed Item
- Unnamed Item
- Graph derivatives
- On the X-join decomposition for undirected graphs
- On certain polytopes associated with graphs
- A Fast Algorithm for the Decomposition of Graphs and Posets
- A Combinatorial Decomposition Theory
- Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
