Finding the prime factors of strong direct product graphs in polynomial time
From MaRDI portal
Publication:686286
DOI10.1016/0012-365X(92)90280-SzbMATH Open0786.68076MaRDI QIDQ686286FDOQ686286
Authors: Joan Feigenbaum, Alejandro A. Schäffer 
Publication date: 14 October 1993
Published in: Discrete Mathematics (Search for Journal in Brave)
Recommendations
- Fast recognition of direct and strong products
- Factoring cardinal product graphs in polynomial time
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Factoring a graph in polynomial time
- Factoring directed graphs with respect to the cardinal product in polynomial time II
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)
Cites Work
- Graph multiplication
- The Kronecker Product of Graphs
- Retracts of hypercubes
- Title not available (Why is that?)
- The Categorical Product of Graphs
- Cartesian graph factorization at logarithmic cost per edge
- Title not available (Why is that?)
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Product graph representations
- Factoring a graph in polynomial time
- Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
- Title not available (Why is that?)
- Cardinal multiplication of structures with a reflexive relation
- On the cancellation law among finite relational structures
- Operations with structures
- Strict refinement for graphs and digraphs
- Das lexikographische Produkt gerichteter Graphen. (The lexicographic product of directed graphs)
- Recognizing Composite Graphs is Equivalent to Testing Graph Isomorphism
- Computing equivalence classes among the edges of a graph with applications
- A note on Winkler's algorithm for factoring a connected graph
- Prefibers and the cartesian product of metric spaces
Cited In (34)
- Factoring a graph in polynomial time
- A local prime factor decomposition algorithm
- Computing equivalence classes among the edges of a graph with applications
- Local algorithms for the prime factorization of strong product graphs
- A theory of decomposition into prime factors of layered interconnection networks
- NZ-flows in strong products of graphs
- Recognizing graph products and bundles
- Direct product primality testing of graphs is GI-hard
- On recognition of strong graph bundles
- Strong products of hypergraphs: unique prime factorization theorems and algorithms
- Approximate graph products
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Factoring directed graphs with respect to the cardinal product in polynomial time II
- The subset-strong product of graphs
- Factoring directed graphs with respect to the cardinal product in polynomial time
- Edge-transitive products
- Asymmetric colorings of products of graphs and digraphs
- Factoring cardinal product graphs in polynomial time
- A prime factor theorem for a generalized direct product
- Strong products of \(\chi\)-critical graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Robust Factorizations and Colorings of Tensor Graphs
- On the chromatic number of the lexicographic product and the Cartesian sum of graphs
- Strong products of Kneser graphs
- On the Cartesian skeleton and the factorization of the strong product of digraphs
- On some metric properties of direct-co-direct product
- Weak reconstruction of strong product graphs
- On distance and strong metric dimension of the modular product
- Graphs S(n, k) and a Variant of the Tower of Hanoi Problem
- Chromatic numbers of the strong product of odd cycles
- Recognizing triangulated Cartesian graph products
- A Heuristic for Direct Product Graph Decomposition
- Coloring graph products---a survey
This page was built for publication: Finding the prime factors of strong direct product graphs in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686286)
