Directed submodularity, ditroids and directed submodular flows

Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

47 Citations (Scopus)


Set relations and operations such as inclusion, union and intersection are generalized to directed subsets whose elements are distinguished between forward and backward elements. The concepts of submodular functions, matroids and polymatroidal network flows are extended to the concepts of directed submodular functions, ditroids and directed submodular flows on directed subsets. Two unrelated matroids (submodular functions) can be embedded in one ditroid (directed submodular function). Total dual integrality is preserved in these generalizations and proved for very general set-function class-directed odd submodular functions.
Original languageEnglish
Pages (from-to)579-599
Number of pages21
JournalMathematical Programming, Series B
Issue number1-3
Publication statusPublished - 1 Apr 1988
Externally publishedYes


  • directed subsets
  • ditroids
  • Submodularity
  • total dual integrality

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Software
  • Management Science and Operations Research
  • Safety, Risk, Reliability and Quality
  • Mathematics(all)
  • Applied Mathematics


Dive into the research topics of 'Directed submodularity, ditroids and directed submodular flows'. Together they form a unique fingerprint.

Cite this