×

Cross-series-parallel digraphs. (English) Zbl 1477.05083

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.

MSC:

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

References:

[1] C. Ambühl, M. Mastrolilli, O. Svensson, Approximating precedence-constrained single machine scheduling by coloring, in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, 2006, pp. 15-26. · Zbl 1155.90373
[2] von Arnim, A.; Schrader, R.; Wang, Y., The permutahedron of N-sparse posets, Math. Program., 75, 1-18 (1996) · Zbl 0871.90039
[3] Bern, M. W.; Lawler, E. L.; Wong, A. L., Linear-time computation of optimal subgraphs of decomposable graphs, J. Algorithms, 8, 2, 216-235 (1987) · Zbl 0618.68058
[4] A. Billstein, R. Schrader, A note on integral generalized flows in generalized series-parallel digraphs, Manuscript, 2019, submitted for publication.
[5] Borie, R. B.; Parker, R. G.; Tovey, C. A., Solving problems on recursively constructed graphs, ACM Comput. Surv., 41, 1, 4:1-4:51 (2009)
[6] Chebolu, P.; Cryan, M.; Martin, R., Exact counting of Euler tours for generalized series-parallel graphs, J. Discrete Algorithms, 10, 110-122 (2012) · Zbl 1241.05048
[7] Chein, M.; Habib, M., The jump number of dags and posets: An introduction, (Hammer, P. L., Combinatorics 79. Combinatorics 79, Annals of Discrete Mathematics, vol. vol. 9 (1980), Elsevier), 189-194 · Zbl 0445.05048
[8] Dushnik, B.; Miller, E. W., Partially ordered sets, Amer. J. Math., 63, 3, 600-610 (1941) · JFM 67.0157.01
[9] Faigle, U.; Lovász, L.; Schrader, R.; Turán, G., Searching in trees, series-parallel and interval orders, SIAM J. Comput., 15, 4, 1075-1084 (1986) · Zbl 0619.68057
[10] Faigle, U.; Schrader, R., On the computational complexity of the order polynomial, Discrete Appl. Math., 15, 2-3, 261-269 (1986) · Zbl 0609.06001
[11] Habib, M.; Jegou, R., N-free posets as generalizations of series-parallel posets, Discrete Appl. Math., 12, 3, 279-291 (1985) · Zbl 0635.06002
[12] Habib, M.; Möhring, R. H., On some complexity properties of N-free posets and posets with bounded decomposition diameter, Discrete Math., 63, 2-3, 157-182 (1987) · Zbl 0608.06004
[13] Harary, F.; Norman, R. Z., Some properties of line digraphs, Rend. Circ. Mat. Palermo (2), 9, 2, 161-168 (1960) · Zbl 0099.18205
[14] Hare, E.; Hedetniemi, S.; Laskar, R.; Peters, K.; Wimer, T., Linear-time computability of combinatorial problems on generalized series-parallel graphs, Discrete Algorithms Complexity, 14, 437-457 (1987) · Zbl 0643.68093
[15] Hopcroft, J. E.; Tarjan, R. E., Isomorphism of planar graphs, (Proceedings of a Symposium on the Complexity of Computer Computations. Proceedings of a Symposium on the Complexity of Computer Computations, March 20-22, 1972 (1972), IBM Thomas J. Watson Research Center: IBM Thomas J. Watson Research Center Yorktown Heights, New York, USA), 131-152 · Zbl 1467.68142
[16] Jakoby, A.; Liśkiewicz, M.; Reischuk, R., Space efficient algorithms for directed series-parallel graphs, J. Algorithms, 60, 2, 85-114 (2006) · Zbl 1100.68080
[17] A. Jakoby, T. Tantau, Logspace algorithms for computing shortest and longest paths in series-parallel graphs, in: Foundations of Software Technology and Theoretical Computer Science, 27th International Conference, FSTTCS 2007, New Delhi, India, December 12-14, 2007, Proceedings, 2007, pp. 216-227. · Zbl 1135.68518
[18] Jamison, B.; Olariu, S., On a unique tree representation for \(P{}_{\text{4}} \)-extendible graphs, Discrete Appl. Math., 34, 1-3, 151-164 (1991) · Zbl 0754.05051
[19] Jamison, B.; Olariu, S., A tree representation for \(P{}_{\text{4}} \)-sparse graphs, Discrete Appl. Math., 35, 2, 115-129 (1992) · Zbl 0763.05092
[20] Jamison, B.; Olariu, S., A linear-time recognition algorithm for \(P{}_{\text{4}} \)-reducible graphs, Theoret. Comput. Sci., 145, 1&2, 329-344 (1995) · Zbl 0873.68155
[21] Kelly, D., The 3-irreducible partially ordered sets, Canad. J. Math., 29, 2, 367-383 (1977) · Zbl 0357.06004
[22] Korneyenko, N., Combinatorial algorithms on a class of graphs, Discrete Appl. Math., 54, 215-217 (1994) · Zbl 0941.68589
[23] Krumke, S. O.; Zeck, C., Generalized max flow in series-parallel graphs, Discrete Optim., 10, 2, 155-162 (2013) · Zbl 1284.90089
[24] Lawler, E., Sequencing jobs to minimize total weighted completion time subject to precedence constraints, (Algorithmic Aspects of Combinatorics. Algorithmic Aspects of Combinatorics, Annals of Discrete Mathematics, vol. 2 (1978), Elsevier), 75-90 · Zbl 0374.68033
[25] Möhring, R., Computationally tractable classes of ordered sets, (Algorithms and Order (1989)), 105-193 · Zbl 1261.06003
[26] Peter, M.; Wambach, G., N-extendible posets, and how to minimize total weighted completion time, Discrete Appl. Math., 99, 1-3, 157-167 (2000) · Zbl 0954.05045
[27] Ruzika, S.; Sperber, H.; Steiner, M., Earliest arrival flows on series-parallel graphs, Networks, 57, 2, 169-173 (2011) · Zbl 1207.90041
[28] Steiner, G., Searching in 2-dimensional partial orders, J. Algorithms, 8, 1, 95-105 (1987) · Zbl 0642.68120
[29] Steiner, G., Minimizing bumps in ordered sets by substitution decomposition, Discrete Math., 76, 3, 285-289 (1989) · Zbl 0676.06002
[30] Takamizawa, K.; Nishizeki, T.; Saito, N., Linear-time computability of combinatorial problems on series-parallel graphs, J. ACM, 29, 3, 623-641 (1982) · Zbl 0485.68055
[31] Valdes, J., Parsing Flowcharts and Series-Parallel Graphs (1978), Stanford University: Stanford University Stanford, CA, USA, (Ph.D. thesis)
[32] Valdes, J.; Tarjan, R.; Lawler, E., The recognition of series parallel digraphs, SIAM J. Comput., 11, 2, 298-313 (1982) · Zbl 0478.68065
[33] Wimer, T. V., Linear Algorithms on K-Terminal Graphs (1987), (Ph.D. thesis) · Zbl 0669.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.