Cross-series-parallel digraphs
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.
- \(N\)-extendible posets, and how to minimize total weighted completion time
- 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
- 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?)
- 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 permutahedron of \(N\)-sparse posets
- The Recognition of Series Parallel Digraphs
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)
