ASTS Orientations on Undirected Graphs: Structural analysis and enumeration
Please always quote using this URN: urn:nbn:de:0297-zib-69632
- All feasible flows in potential-driven networks induce an orientation on the undirected graph underlying the network. Clearly, these orientations must satisfy two conditions: they are acyclic and there are no "dead ends" in the network, i.e. each source requires outgoing flows, each sink requires incoming flows, and each transhipment vertex requires both an incoming and an outgoing flow. In this paper we will call orientations that satisfy these conditions acyclic source-transhipment-sink orientations (ASTS-orientation) and study their structure. In particular, we characterize graphs that allow for such an orientation, describe a way to enumerate all possible ASTS-orientations of a given graph, present an algorithm to simplify and decompose a graph before such an enumeration and shed light on the role of zero flows in the context of ASTS-orientations.
Author: | Kai-Helge Becker, Benjamin HillerORCiD |
---|---|
Document Type: | ZIB-Report |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
Date of first Publication: | 2018/07/25 |
Series (Serial Number): | ZIB-Report (18-31) |
ISSN: | 1438-0064 |