Partitioning the edge set of a bipartite graph into chain packings: Complexity of some variations. (English) Zbl 1028.05061

The author extends the decomposition theorem of Birkhoff-von Neumann for nonnegative matrices with constant row and column sums to integral matrices whose entries can be positive or negative. In graph-theoretical interpretation, instead of matchings we have collections of oriented paths with disjoint end nodes.


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15B51 Stochastic matrices
Full Text: DOI


[1] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[2] Blazewicz, J.; Ecker, K. H.; Pesch, E.; Schmidt, G.; Weglarz, J., Scheduling Computer and Manufacturing Processes (1966), Springer-Verlag: Springer-Verlag New York
[3] Brualdi, R. A., Some application of doubly stochastic matrices, Linear Algebra Appl., 107, 77-110 (1988) · Zbl 0657.15016
[4] Burkard, R. E., On time-slot assignments for TDMA systems, Computing, 35, 99-112 (1985) · Zbl 0559.90056
[6] de Werra, D.; Hoffman, A. J.; Mahadev, N. V.R.; Peled, U. N., Restrictions and preassignments in preemptive open shop scheduling, Discrete Appl. Math., 68, 169-188 (1996) · Zbl 0846.90056
[7] de Werra, D., A few remarks on chromatic scheduling, (Roy, B., Combinatorial Programming: Methods and Applications (1975), D. Reidel Publ. Co: D. Reidel Publ. Co Dordrecht), 337-342
[8] de Werra, D., Equitable colorations of graphs, Rev. Fr. d’Inform. Recher. Opération., R-3, 3-8 (1971) · Zbl 0239.05112
[9] de Werra, D., A note on SS/TDMA satellite communication, Linear Algebra Appl., 135, 60-77 (1990) · Zbl 0702.90042
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.