On BF-orderable graphs
type: Item
instance of: scholarly article
title: On BF-orderable graphs
zbMATH Open document ID: 0605.05025
DOI: 10.1016/0166-218X(86)90051-X
author: K. Mehlhorn
author: Bernd H. Schmidt
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: A directed graph G is BF-orderable w.r.t. a vertex s if there exists an ordering of the edges such that on any simple path starting from s the edges occur increasingly. This generalization of acyclic graphs enables a linear time algorithm for the single source shortest path problem. An entry point (w.r.t. s) of a subgraph S of G is a vertex w of S s.t. there exists a simple path from s to w using no other node of S. The following characterization of BF-orderable graphs is proven: Any simple cycle has at most two entry points. Any two simple paths starting at s pass through any two common vertices in the same order. It is also indicated how to check BF-orderability in quadratic time, but this may not be a tight bound.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 3977037
zbMATH Keywords: acyclic graphs
zbMATH Keywords: linear time algorithm
zbMATH Keywords: shortest path
zbMATH Keywords: BF-orderable graphs
reviewed by: Frank Plastria
MaRDI profile type: Publication
cites work: On a routing problem
cites work: Optimal Placement for River Routing
cites work: Q4195958
full work available at URL: 0166-218x(86)90051-x
OpenAlex ID: W2049855476
description: scientific article; zbMATH DE number 3977037