Orientations with single source and sink
Given a graph G and a pair of vertices s and t, linear time algorithms are formulated for finding orientations D of G such that D has a unique source s and sink t, i.e., D has unique vertices s and t of zero indegree and zero outdegree, respectively. The additional requirement that D be acyclic is also considered. Necessary and sufficient conditions for the existence of the orientations are given.
scientific article; zbMATH DE number 3896960