On BF-orderable graphs (Q1084116)

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.