On the Langberg-Médard k-Unicast Conjecture with $k=3,4$
Kai Cai, Guangyue Han · 2018
The Langberg-Médard k-Unicast Conjecture states that for any strongly reachable k-pair network, there exists a multi-flow with rate (1, 1, ..., 1). In this paper, for k=3,4, we construct multi-flows with rate ([11/12], [11/12],..., [11/12]), which improves the previous result ([8/9], [8/9], ..., [8/9]), and we further prove that our constructions are optimal within the proposed framework.