TY - GEN
A1 - Becker, Kai Helge
A1 - Hiller, Benjamin
T1 - ASTS Orientations on Undirected Graphs: Structural analysis and enumeration
N2 - 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.
T3 - ZIB-Report - 18-31
Y1 - 2018
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6963
UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-69632
SN - 1438-0064
ER -