Partitioning the edge set of a bipartite graph into chain packings: Complexity of some variations

DOI10.1016/S0024-3795(02)00691-2MaRDI QIDQ1399253zbMATH OpenOpenAlexFDO

Authors Dominique De Werra

Publication date 30 July 2003

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0024-3795(02)00691-2

zbMATH Keywords

balancing of cardinalitiesdoubly stochastic matricesequitable coloringspermutation matrices

Mathematics Subject Classification ID

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

Review text

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.

Recommendations

• Path colorings in bipartite graphs
• On the complexity of some edge-partition problems for graphs
• Decomposition of bipartite graphs under degree constraints
• On partitioning two matroids into common independent subsets
• scientific article; zbMATH DE number 4148138

Cites work

• A note on SS/TDMA satellite communication
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3491001 (Why is no real title available?)
• scientific article; zbMATH DE number 3378938 (Why is no real title available?)
• Restrictions and preassignments in preemptive open shop scheduling
• Some applications of doubly stochastic matrices
• Time-slot assignment for TDMA-systems
• Variations on the theorem of Birkhoff-von Neumann and extensions

Cited in

(2)

• Path colorings in bipartite graphs
• Equitable partitions into matchings and coverings in mixed graphs

This page was built for publication: Partitioning the edge set of a bipartite graph into chain packings: Complexity of some variations

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