Greedy packing and series-parallel graphs (Q1110543): Difference between revisions

A series-parallel graph G is a directed multigraph with a single source and single sink such that if the number of edges in G, \(| E(G)| >1\) then G is obtained from a series-parallel graph G' with \(| E(G')=| E(G)| -1\) by replacing some edge (u,v) of G' by (1) two copies of this edge \((u,v)_ 1\), \((u,v)_ 2\) or (2) two edges (u,w) and (w,v) where w is a new vertex. Using series-parallel graphs the authors characterize the non-negative matrices A of the linear programming problem (packing problem): for every \(a\geq 0\), max(1,y) where Ay\(\leq a\), \(y\geq 0\) is solved by maximizing the variables in arbitrary order.