Orientations with single source and sink (Q1057281)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Orientations with single source and sink |
scientific article; zbMATH DE number 3896960
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Orientations with single source and sink |
scientific article; zbMATH DE number 3896960 |
Statements
Orientations with single source and sink (English)
0 references
1985
0 references
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.
0 references
digraph
0 references
degree
0 references
orientations
0 references
indegree
0 references
outdegree
0 references
