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

de Werra, D.

Linear Algebra Appl. 368, 315-327 (2003).

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.

Reviewer: Dragoš Cvetković (Beograd)

MSC:

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

Keywords:

doubly stochastic matrices; equitable colorings; balancing of cardinalities; permutation matrices

References:

[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