Computing equivalence classes among the edges of a graph with applications

✍ Scribed by Franz Aurenhammer; Johann Hagauer

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 896 KB
• Volume: 109
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90274-j

✦ Synopsis

classes among the edges of a graph For two edges e = (x, y) and e ' = (x', y') of a connected graph G = (V, E) let e Oe' iff d(x. x') + ;(y, y') # 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 6 of 0 in time O((Vl IEI) and space O(lVl'). Finding the equivalence classes of 6 is the primary step of several graph algorithms. ' Factoring from 6 is achieved in O(mn) time and O(m) space by Feder's [4] recent method, as was pointed out by the referees. Subsequent to the present papet, an O(m log rm)-time and O(m)-space factorization algorithm that circumvents the computation of 0 was developed by the authors jointly with W. Imrich [Z].