Finding the prime factors of strong direct product graphs in polynomial time

DOI10.1016/0012-365X(92)90280-SzbMATH Open0786.68076MaRDI QIDQ686286FDOQ686286

Joan Feigenbaum, Alejandro A. Schäffer

Publication date: 14 October 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

polynomial complexitydecomposition algorithmstrong direct product of graphs

Mathematics Subject Classification ID

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph multiplication
• The Kronecker Product of Graphs
• Retracts of hypercubes
• The Categorical Product of Graphs
• Cartesian graph factorization at logarithmic cost per edge
• 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
• 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 (27)

• A local prime factor decomposition algorithm
• Computing equivalence classes among the edges of a graph with applications
• 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
• Factoring directed graphs with respect to the cardinal product in polynomial time II
• The subset-strong product of graphs
• Edge-transitive products
• Asymmetric colorings of products of graphs and digraphs
• Factoring cardinal product graphs in polynomial time
• Strong products of \(\chi\)-critical graphs
• Title not available (Why is that?)
• 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
• Recognizing triangulated Cartesian graph products
• 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)