Cross-series-parallel digraphs

DOI10.1016/J.DAM.2020.12.012MaRDI QIDQ1983112zbMATH OpenOpenAlexFDO

Authors Jorin Dornemann, Rainer Schrader

Publication date 15 September 2021

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

Full work available at URL https://doi.org/10.1016/j.dam.2020.12.012

zbMATH Keywords

decompositiondirected graphseries-parallelChurch-Rosser property

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Ordered sets (06A99) Networks and circuits as models of computation; circuit complexity (68Q06)

Recommendations

• Parallel recognition of series-parallel graphs
• scientific article; zbMATH DE number 140481
• Space efficient algorithms for directed series–parallel graphs
• scientific article; zbMATH DE number 1689046
• How to draw a series-parallel digraph

Cites work

• scientific article; zbMATH DE number 4049086 (Why is no real title available?)
• scientific article; zbMATH DE number 4095510 (Why is no real title available?)
• scientific article; zbMATH DE number 6157240 (Why is no real title available?)
• A linear-time recognition algorithm for \(P_{4}\)-reducible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Approximating Precedence-Constrained Single Machine Scheduling by Coloring
• Combinatorial algorithms on a class of graphs
• Earliest arrival flows on series-parallel graphs
• Exact counting of Euler tours for generalized series-parallel graphs
• Generalized max flow in series-parallel graphs
• Isomorphism of planar graphs (working paper)
• Linear-time computability of combinatorial problems on series-parallel graphs
• Linear-time computation of optimal subgraphs of decomposable graphs
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Minimizing bumps in ordered sets by substitution decomposition
• N-free posets as generalizations of series-parallel posets
• On a unique tree representation for \(P_ 4\)-extendible graphs
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• On the computational complexity of the order polynomial
• Searching in 2-dimensional partial orders
• Searching in Trees, Series-Parallel and Interval Orders
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Some properties of line digraphs
• Space efficient algorithms for directed series–parallel graphs
• The 3-Irreducible Partially Ordered Sets
• The Jump Number of Dags and Posets: An Introduction
• The Recognition of Series Parallel Digraphs
• The permutahedron of \(N\)-sparse posets
• \(N\)-extendible posets, and how to minimize total weighted completion time

Cited in

(2)

• Linkless symmetric drawings of series parallel digraphs
• Chronological rectangle digraphs which are two-terminal series-parallel

This page was built for publication: Cross-series-parallel digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1983112)