Distances in and Layering of a DAG
share
The diameter of an undirected unweighted graph G=(V,E) is the maximum value of the distance from any vertex u to another vertex v for u,v ∈ V where distance i.e. d(u,v) is the length of the shortest path from u to v in G. DAG, is a directed graph without a cycle. We denote the diameter of an unweighted DAG G=(V,E) by δ (G). The stretch of a DAG G is the length of longest path from u to v in G, for all choices of (u, v) ∈ V denoted by Δ (G). The diameter of an undirected graph can be computed in O(|V|(|V|+|E|)) time by executing breadth first search |V| times. We show that stretch and diameter of a DAG can be computed in O(|V|+|E|) time and O(|V||E|) time respectively. A DAG is balanced if and only if a consistent assignment of level numbers to all vertices is possible. Layering refers to such an assignment. A balanced DAG is defined. An efficient algorithm that either detects whether a given DAG is unbalanced or layers it otherwise is designed with a running time of O(|V|+|E|). Key words: Diameter, directed acyclic graph, longest directed path, graph algorithms, complexity.
READ FULL TEXT