Orientations with single source and sink
type: Item
instance of: scholarly article
title: Orientations with single source and sink
zbMATH Open document ID: 0563.05026
DOI: 10.1016/0166-218X(85)90052-6
author: Ronaldo C. M. Persiano
author: Antonio A. F. Oliveira
author: Jayme L. Szwarcfiter
published in: Discrete Applied Mathematics
publication date: 1985-01-01T00:00:00Z
review text: 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.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 3896960
zbMATH Keywords: digraph
zbMATH Keywords: degree
zbMATH Keywords: orientations
zbMATH Keywords: indegree
zbMATH Keywords: outdegree
MaRDI profile type: Publication
cites work: Q3880849
cites work: A Theorem on Graphs, with an Application to a Problem of Traffic Control
cites work: Depth-First Search and Linear Graph Algorithms
description: scientific article; zbMATH DE number 3896960