A characterization of network representable polymatroids |
| |
Authors: | W. W. Bein P. Brucker M. F. M. Stallmann |
| |
Affiliation: | (1) Computer Science Department, University of New Mexico, 87131 Albuquerque, New Mexico, USA;(2) Fachbereich Mathematik/Informatik, Universität Osnabrück, Germany;(3) Computer Science Department, North Carolina State University, 27695 Raleigh, NC, USA |
| |
Abstract: | Meggido [1974] showed that the maximum flow through sets of sources in a multiple sink flow network is a polymatroidal function. Recently, Federgruen and Groenevelt [1985], [1986] have considered polymatroids that can be represented by a multiple source flow network and have improved the runnung time of an important scheduling application.We give a characterization of network representability and relate representable polymatroids to the theory of gammoids.
Zusammenfassung Meggido [1974] hat gezeigt, daß ein maximaler Fluß durch ein Netzwerk mit mehrfachen Senken eine polymatroidale Funktion beschreibt. Federgruen und Groenvelt [1985], [1986] haben kürzlich solche Polymatroide betrachtet, die durch Flüsse in derartigen Netzwerken repräsentiert werden können und haben so die Laufzeit einer wichtigen Schedulinganwendung verbessern können.Wir geben eine Charakterisierung von Funktionen, die durch derartige Netzflußnetzwerke realisierbar sind. Dabei stellen wir eine Verbindung her zwischen Repräsentierbarkeit und Gammoidtheorie. |
| |
Keywords: | Network Flows Polymatroids Submodular Functions Gammoids Network Representability |
本文献已被 SpringerLink 等数据库收录! |
|