# Computing equivalence classes among the edges of a graph with applications

F. Aurenhammer and J. Hagauer

### Abstract:

For two edges and of a connected graph let iff . Here denotes the length of a shortest path in joining vertices and . An algorithm is presented that computes the equivalence classes induced on by the transitive closure of in time and space . Finding the equivalence classes of 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.