✦ LIBER ✦

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

✍ Scribed by D. de Werra

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 154 KB
Volume: 368
Category: Article
ISSN: 0024-3795
DOI: 10.1016/s0024-3795(02)00691-2

No coin nor oath required. For personal study only.

✦ Synopsis

An extension of the decomposition theorem of Birkhoff-von Neumann theorem is given for the case where entries can be positive or negative. The special case of an integral matrix is discussed and some balancing properties which are trivial for the classical case (non-negative entries only in the matrix) are shown to be NP-complete. Some relaxations are presented for solving the balancing problem.