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)

zbMATH Keywords

graph algorithmsequivalence classesisometric embeddability

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 139782 (Why is no real title available?)
• 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
• Isometric embedding in products of complete graphs
• On Isometric Embeddings of Graphs
• Product graph representations

Cited in

(8)

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

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)