Orientations with single source and sink

DOI10.1016/0166-218X(85)90052-6MaRDI QIDQ1057281zbMATH OpenFDO

Authors Ronaldo C. M. Persiano, Antonio A. F. Oliveira, Jayme L. Szwarcfiter

Publication date 1985

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(85)90052-6

zbMATH Keywords

degreedigraphindegreeorientationsoutdegree

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Graph theory (05C99)

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.

Recommendations

• On orientations and shortest paths
• scientific article; zbMATH DE number 637327
• Efficient enumeration of graph orientations with sources
• Strong orientations without even directed circuits
• Listing Acyclic Orientations of Graphs with Single and Multiple Sources

Cites work

• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)

Cited in

(5)

• On orientations and shortest paths
• A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid
• Efficient enumeration of graph orientations with sources
• Exact controllability of the wave equation on graphs
• Unilateral orientation of mixed graphs

This page was built for publication: Orientations with single source and sink

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1057281)