Cartesian graph factorization at logarithmic cost per edge
From MaRDI portal
Publication:1210332
DOI10.1007/BF01200428zbMath0770.68064OpenAlexW1992112020WikidataQ56688307 ScholiaQ56688307MaRDI QIDQ1210332
Wilfried Imrich, Franz Aurenhammer, Johann Hagauer
Publication date: 8 August 1993
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01200428
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (22)
Isomorphism between circulants and Cartesian products of cycles ⋮ Algorithm for recognizing Cartesian graph bundles ⋮ Recognizing Hamming graphs in linear time and space ⋮ Strong products of Kneser graphs ⋮ Recognizing Cartesian graph bundles ⋮ Recognizing Cartesian products in linear time ⋮ On the Hadwiger's conjecture for graph products ⋮ On the weak reconstruction of Cartesian-product graphs ⋮ Recognizing some complementary products ⋮ Fast factorization of Cartesian products of (directed) hypergraphs ⋮ Recognizing triangulated Cartesian graph products ⋮ On Cartesian products of signed graphs ⋮ On isomorphism between circulant and Cartesian product of 2 cycles ⋮ Finding the prime factors of strong direct product graphs in polynomial time ⋮ Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs ⋮ Optimal acyclic edge colouring of grid like graphs ⋮ Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time ⋮ Strong products of \(\chi\)-critical graphs ⋮ Hadwiger number and the Cartesian product of graphs ⋮ Modular decomposition of graphs and the distance preserving property ⋮ Lattice fermions as spectral graphs ⋮ Factoring cardinal product graphs in polynomial time
Cites Work
- Unnamed Item
- Factoring a graph in polynomial time
- Computing equivalence classes among the edges of a graph with applications
- A note on Winkler's algorithm for factoring a connected graph
- Graph multiplication
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
- On Isometric Embeddings of Graphs
- Product graph representations
This page was built for publication: Cartesian graph factorization at logarithmic cost per edge
