The edge versus path incidence matrix of series-parallel graphs and greedy packing

Alan J. Hoffman, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

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 the max flow problem in series-parallel graphs, as shown by Bein et al. (Discrete 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 optimally using a greedy algorithm with any permutation on the variables if and only if the (0,1) matrix is the edge versus path incidence matrix of a series parallel graph. Thus, our algorithm can be applied to check whether such a packing problem is solvable greedily.

Original languageEnglish (US)
Pages (from-to)275-284
Number of pages10
JournalDiscrete Applied Mathematics
Volume113
Issue number2-3
DOIs
StatePublished - Oct 15 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Edge versus path incidence matrix
  • Greedy algorithms
  • Incidence matrix
  • Packing problems
  • Series parallel graphs

Fingerprint Dive into the research topics of 'The edge versus path incidence matrix of series-parallel graphs and greedy packing'. Together they form a unique fingerprint.

Cite this