Computing equivalence classes among the edges of a graph with applications

F. Aurenhammer and J. Hagauer

Abstract:

For two edges $e=(x,y)$ and $e'=(x',y')$ of a connected graph $G=(V,E)$ let $e
\Theta e'$ iff $d(x,x') + d(y,y') \neq d(x,y') + d(x',y)$. Here $d(x,y)$ denotes the length of a shortest path in $G$ joining vertices $x$ and $y$. An algorithm is presented that computes the equivalence classes induced on $E$ by the transitive closure $\hat{\Theta}$ of $\Theta$ in time $O(\vert V\vert\vert E\vert)$ and space $O(\vert V\vert^2)$. Finding the equivalence classes of $\hat{\Theta}$ is the primary step of several graph algorithms.



Reference: F. Aurenhammer and J. Hagauer. Computing equivalence classes among the edges of a graph with applications. In Proc. Int'l Conf. Algebraic Graph Theory, page 11, Leibnitz, Austria, 1989.