Decomposition of Directed Graphs

DOI10.1137/0603021zbMath0497.05031OpenAlexW2106818977MaRDI 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

zbMATH Keywords

strongly connected digraph indecomposable digraphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20)

Related Items

A polynomial kernel for 3-leaf power deletion ⋮ From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals ⋮ Circle graph isomorphism in almost linear time ⋮ Dynamic Distance Hereditary Graphs Using Split Decomposition ⋮ Graphs with bounded induced distance ⋮ Domination graphs: Examples and counterexamples ⋮ A structure theorem for graphs with no cycle with a unique chord and its consequences ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graph isomorphism restricted by lists ⋮ A Representation Theorem for Union-Difference Families and Application ⋮ BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION ⋮ The graph sandwich problem for 1-join composition is NP-complete ⋮ Isotropic matroids. III: Connectivity ⋮ Minimally 3-connected isotropic systems ⋮ Between treewidth and clique-width ⋮ Solving Problems on Graphs of High Rank-Width ⋮ On finding the jump number of a partial order by substitution decomposition ⋮ A BRACKET POLYNOMIAL FOR GRAPHS, IV: UNDIRECTED EULER CIRCUITS, GRAPH-LINKS AND MULTIPLY MARKED GRAPHS ⋮ Efficient parallel recognition algorithms of cographs and distance hereditary graphs ⋮ N-free posets as generalizations of series-parallel posets ⋮ An $O(n^ 2)$ incremental algorithm for modular decomposition of graphs and 2-structures ⋮ Isotropic systems ⋮ Topology and counting of real algebraic curves ⋮ Connectivity and $\beta$-invariants of isotropic systems and 4-regular graphs ⋮ Notes on a theorem of Naji ⋮ 2-nested matrices: towards understanding the structure of circle graphs ⋮ On submodular function minimization ⋮ The rank-width of edge-coloured graphs ⋮ Graphic presentations of isotropic systems ⋮ Applying clique-decomposition for computing Gromov hyperbolicity ⋮ Reducing prime graphs and recognizing circle graphs ⋮ A matrix description of weakly bipartitive and bipartitive families ⋮ On the closure of graphs under substitution ⋮ $P_ 4$-comparability graphs ⋮ Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions ⋮ Networks with small stretch number ⋮ Grammars and clique-width bounds from split decompositions ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ Between Treewidth and Clique-Width ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ Minimal strong digraphs ⋮ Meta-kernelization with structural parameters ⋮ Tree-representation of set families and applications to combinatorial decompositions ⋮ Reduced clique graphs of chordal graphs ⋮ PC trees and circular-ones arrangements. ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ Polynomial-time recognition of clique-width $\leq 3$ graphs ⋮ Prechains and self duality ⋮ MAD trees and distance-hereditary graphs ⋮ Digraph Decompositions and Eulerian Systems ⋮ $(\leq k)$-reconstructible binary relations ⋮ Solving problems on graphs of high rank-width ⋮ Distance labeling scheme and split decomposition ⋮ Partial characterizations of circle graphs ⋮ Decomposition of partial orders ⋮ Matroids that classify forests ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Practical and efficient circle graph recognition ⋮ Practical and efficient split decomposition via graph-labelled trees ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ A BRACKET POLYNOMIAL FOR GRAPHS, III: VERTEX WEIGHTS ⋮ Enumerations, forbidden subgraph characterizations, and the split-decomposition ⋮ The $b$-\textsc{Matching} problem in distance-hereditary graphs and beyond ⋮ Mutant knots and intersection graphs ⋮ Weighted Interlace Polynomials ⋮ Circle graphs and monadic second-order logic ⋮ Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way ⋮ Solving some NP-complete problems using split decomposition ⋮ Polynomial-time algorithm for isomorphism of graphs with clique-width at most three ⋮ $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs ⋮ On complexities of minus domination ⋮ Recognizing locally equivalent graphs ⋮ $P_ 4$-trees and substitution decomposition ⋮ The external constraint 4 nonempty part sandwich problem ⋮ Distance-hereditary comparability graphs ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ The modular decomposition of countable graphs. Definition and construction in monadic second-order logic ⋮ Diamond-free circle graphs are Helly circle ⋮ $O(m\log n)$ split decomposition of strongly-connected graphs ⋮ Compositions for perfect graphs ⋮ Recognizability, hypergraph operations, and logical types ⋮ A 2-isomorphism theorem for delta-matroids ⋮ Basic perfect graphs and their extensions ⋮ A contract-based model for directed network formation ⋮ Splitting cubic circle graphs ⋮ Isotropic matroids. I: Multimatroids and neighborhoods ⋮ Clique-width of graphs defined by one-vertex extensions ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ Scattered Classes of Graphs ⋮ Unavoidable vertex-minors in large prime graphs ⋮ Excluded vertex-minors for graphs of linear rank-width at most $k$ ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Decomposition of k-ary relations ⋮ On an extension of distance hereditary graphs ⋮ Treelike comparability graphs ⋮ On Computing the Gromov Hyperbolicity ⋮ O(m logn) Split Decomposition of Strongly Connected Graphs ⋮ Distance-Hereditary Comparability Graphs ⋮ The strong perfect graph conjecture: 40 years of attempts, and its resolution ⋮ Digraphs of Bounded Width ⋮ Decomposition of submodular functions ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ A decomposition of distributive lattices ⋮ Graph decompositions definable in monadic second-order logic ⋮ The bi-join decomposition ⋮ Rank connectivity and pivot-minors of graphs ⋮ An algorithm for minimizing setups in precedence constrained scheduling ⋮ Some results on more flexible versions of Graph Motif ⋮ Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter

Cites Work

This page was built for publication: Decomposition of Directed Graphs