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.
- directed subsets
- total dual integrality
ASJC Scopus subject areas
- Computer Graphics and Computer-Aided Design
- Management Science and Operations Research
- Safety, Risk, Reliability and Quality
- Applied Mathematics