On Circuit Valuation of Matroids

Kazuo Murota, Akihisa Tamura

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)


The concept of valuated matroids was introduced by Dress and Wenzel as a quantitative extension of the base exchange axiom for matroids. This paper gives several sets of cryptomorphically equivalent axioms of valuated matroids in terms of (R∪{-∞})-valued vectors defined on the circuits of the underlying matroid, where R is a totally ordered additive group. The dual of a valuated matroid is characterized by an orthogonality of (R∪{-∞})-valued vectors on circuits. Minty's characterization for matroids by the painting property is generalized for valuated matroids.

Original languageEnglish
Pages (from-to)192-225
Number of pages34
JournalAdvances in Applied Mathematics
Issue number3
Publication statusPublished - 2001 Apr
Externally publishedYes


  • Bases
  • Circuits
  • Duality
  • Valuated matroids

ASJC Scopus subject areas

  • Applied Mathematics


Dive into the research topics of 'On Circuit Valuation of Matroids'. Together they form a unique fingerprint.

Cite this