Aj. Hoffman et B. Schieber, The edge versus path incidence matrix of series-parallel graphs and greedypacking, DISCR APP M, 113(2-3), 2001, pp. 275-284
We characterize the edge versus path incidence matrix of a series-parallel
graph. One characterization is algorithmic while the second is structural.
The structural characterization implies that the greedy algorithm solves th
e max flow problem in series-parallel graphs, as shown by Bein et al. (Disc
rete Appl. Math. 10 (1985) 117-124). The algorithmic characterization gives
an efficient way to identify such matrices. Hoffman and Tucker (J. Combin.
Theory Ser. A 47 (1988) 6-5). proved that a packing problem defined by a (
0,1) matrix in which no column contains another column can be solved optima
lly using a greedy algorithm with any permutation on the variables if and o
nly if the (0,1) matrix is the edge versus path incidence matrix of a serie
s parallel graph. Thus, our algorithm can be applied to check whether such
a packing problem is solvable greedily. (C) 2001 Elsevier Science B.V. All
rights reserved.