6963
eng
reportzib
0
--
2018-07-25
--
ASTS Orientations on Undirected Graphs: Structural analysis and enumeration
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.
1438-0064
urn:nbn:de:0297-zib-69632
Kai Helge Becker
Benjamin Hiller
Benjamin Hiller
ZIB-Report
18-31
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
MODAL-GasLab
MODAL-Gesamt
Becker, Kai-Helge
ECMATH-MI10
https://opus4.kobv.de/opus4-zib/files/6963/ZR-18-31ZIB.pdf