Computing equivalence classes among the edges of a graph with applications

DOI10.1016/0012-365X(92)90274-JMaRDI QIDQ686277zbMATH OpenFDO

Authors Franz Aurenhammer, Johann Hagauer

Publication date 14 October 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(92)90274-J

zbMATH Keywords

equivalence classesgraph algorithmsisometric embeddability

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 1138598
• Hypergraph isomorphism and structural equivalence of Boolean functions
• scientific article; zbMATH DE number 1086495
• On a special restriction of a reflexive and symmetric relation to an equivalence relation
• scientific article; zbMATH DE number 139779
• McKay's canonical graph labeling algorithm
• Succinct data structures for representing equivalence classes
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Congruence relations of paths: some combinatorial properties
• scientific article; zbMATH DE number 2123426

Cites work

• A note on Winkler's algorithm for factoring a connected graph
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Distance-preserving subgraphs of hypercubes
• Factoring a graph in polynomial time
• Finding the prime factors of strong direct product graphs in polynomial time
• Graph multiplication
• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 139782 (Why is no real title available?)
• Isometric embedding in products of complete graphs
• On Isometric Embeddings of Graphs
• Product graph representations

Cited in

(8)

• Cartesian graph factorization at logarithmic cost per edge
• Faster isometric embedding in products of complete graphs
• scientific article; zbMATH DE number 5291590 (Why is no real title available?)
• Factoring cartesian‐product graphs
• Recognizing binary Hamming graphs inO(n 2 logn) time
• The complement of the Djoković-Winkler relation
• Finding the prime factors of strong direct product graphs in polynomial time
• A note on Winkler's algorithm for factoring a connected graph

This page was built for publication: Computing equivalence classes among the edges of a graph with applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686277)