Cross-series-parallel digraphs
type: Item
instance of: scholarly article
title: Cross-series-parallel digraphs
zbMATH Open document ID: 1477.05083
author: Jorin Dornemann
author: Rainer Schrader
published in: Discrete Applied Mathematics
publication date: 2021-09-15T00:00:00Z
review text: By restricting to the class of series-parallel graphs or digraphs, many hard problems can be shown to be solvable in polynomial time. The series-parallel digraphs come in two versions, the vertex version and the edge version. In fact, both versions can be transferred into each other by the reverse line digraph construction. This is possible because series-parallel digraphs are a subclass of the so-called CBC-digraphs, where CBC-digraphs are precisely the class of digraphs for which line digraphs exist. Series-parallel digraphs have already been generalized in various directions. Some of the generalizations control the structure of certain emerging induced subdigraphs called N's. In the present paper, the authors concentrate on another generalization of directed series-parallel digraphs, where the structure of induced N's is much less controlled, the so-called cross-series-parallel digraphs. It is shown that this class of directed digraphs can efficiently be recognized by a decomposition approach, and this decomposition is not unique and does not lead to a tree but a planar graph.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68Q06
Mathematics Subject Classification ID: 06A99
zbMATH DE Number: 7395727
zbMATH Keywords: directed graph
zbMATH Keywords: series-parallel
zbMATH Keywords: decomposition
zbMATH Keywords: Church-Rosser property
MaRDI profile type: Publication
full work available at URL: j.dam.2020.12.012
OpenAlex ID: W3118101106
cites work: Approximating Precedence-Constrained Single Machine Scheduling by Coloring
cites work: The permutahedron of \(N\)-sparse posets
cites work: Linear-time computation of optimal subgraphs of decomposable graphs
cites work: Exact counting of Euler tours for generalized series-parallel graphs
cites work: The Jump Number of Dags and Posets: An Introduction
cites work: Searching in Trees, Series-Parallel and Interval Orders
cites work: On the computational complexity of the order polynomial
cites work: N-free posets as generalizations of series-parallel posets
cites work: On some complexity properties of N-free posets and posets with bounded decomposition diameter
cites work: Some properties of line digraphs
cites work: Q3785978
cites work: Isomorphism of Planar Graphs (Working Paper)
cites work: Space efficient algorithms for directed series–parallel graphs
cites work: Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
cites work: On a unique tree representation for \(P_ 4\)-extendible graphs
cites work: A tree representation for \(P_ 4\)-sparse graphs
cites work: A linear-time recognition algorithm for \(P_{4}\)-reducible graphs
cites work: The 3-Irreducible Partially Ordered Sets
cites work: Combinatorial algorithms on a class of graphs
cites work: Generalized max flow in series-parallel graphs
cites work: Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
cites work: Q4918387
cites work: \(N\)-extendible posets, and how to minimize total weighted completion time
cites work: Earliest arrival flows on series-parallel graphs
cites work: Searching in 2-dimensional partial orders
cites work: Minimizing bumps in ordered sets by substitution decomposition
cites work: Linear-time computability of combinatorial problems on series-parallel graphs
cites work: The Recognition of Series Parallel Digraphs
cites work: Q3822197
DOI: 10.1016/J.DAM.2020.12.012
description: scientific article; zbMATH DE number 7395727