Capacity-obeying packing

From Egres Open
Jump to: navigation, search

Let G=(V,E) be an undirected or directed graph, and [math]c:E \to {\mathbb Z}_+[/math] a capacity function on the edges. A capacity-obeying packing of subgraphs is a collection [math]G_1, \ldots, G_t[/math] of subgraphs of G with the property that each edge [math]e\in E[/math] is contained in at most c(e) of these subgraphs. An analogous definition can be given for hypergraphs.