Directed submodularity, ditroids and directed submodular flows

Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

44 Citations (Scopus)

Abstract

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
Volume42
Issue number1-3
DOIs
Publication statusPublished - 1 Apr 1988
Externally publishedYes

Keywords

  • 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

Cite this