On the spanning tree polyhedron

Sunil Chopra*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

41 Scopus citations


Fulkerson [4] characterized the blocking matrix to the incidence matrix of all spanning trees of the graph. This paper gives a simple constructive proof of this characterization using a minimum spanning tree algorithm. We also identify all inequalities that are facets.

Original languageEnglish (US)
Pages (from-to)25-29
Number of pages5
JournalOperations Research Letters
Issue number1
StatePublished - Feb 1989


  • facets
  • polyhedron
  • spanning tree

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On the spanning tree polyhedron'. Together they form a unique fingerprint.

Cite this