Computing equivalence classes among the edges of a graph with applications (Q686277): Difference between revisions

Let \(G=(V,E)\) be an undirected graph. We denote by \(d(x,y)\) the length of a shortest path in \(G\) between \(x\) and \(y\). Define a relation \(\Theta\) on \(E \times E\) as follows: for two edges \(e=xy\) and \(e'=x'y'\) we let \(e\Theta e' \text{ if and only if } d(x,x') + d(y,y') \neq d(x,y')+d(x',y).\) This relation was introduced by Graham and Winkler [\textit{R. L. Graham} and \textit{P. M. Winkler}, On isometric embeddings of graphs, Trans. Am. Math. Soc. 288, 527-536 (1985; Zbl 0576.05017)]. It is easy to check that \(\Theta\) is reflexive and symmetric, but not in general transitive. Hence the transitive closure \(\widehat \Theta\) is an equivalence relation. This paper is concerned with finding the equivalence classes of \(E\) with respect to \(\widehat \Theta\). A method is described which allows to find these in time \(O (| V | | E |)\) using \(O (| V |^ 2)\) space. This should be compared to the obvious algorithm with complexity \(O (| E |^ 2)\) with \(O (| V |^ 2)\) space. The authors remark that Feder [\textit{T. Feder}, Product graph representations, J. Graph Theory 16, No. 5, 467-488 (1992; Zbl 0766.05092)] has improved the space requirement to \(O (| E |)\). Computing these equivalence classes is a first step in several graph algorithms. As examples the authors mention isometric embeddability in hypercubes and factoring a Cartesian product.