Direct product primality testing of graphs is GI-hard

DOI10.1016/j.tcs.2021.01.029zbMath1502.68214arXiv2003.01591OpenAlexW3122115655MaRDI QIDQ1998840

Luca Calderoni, Moreno Marzolla, Luciano Margara

Publication date: 9 March 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2003.01591

zbMATH Keywords

Kronecker productgraph isomorphismgraph factorizationGI-complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph operations (line graphs, products, etc.) (05C76)

Related Items (1)

A Heuristic for Direct Product Graph Decomposition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factoring a graph in polynomial time
• Finding the prime factors of strong direct product graphs in polynomial time
• Graph multiplication
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Factoring cardinal product graphs in polynomial time
• The Kronecker Product of Graphs
• Recognizing Composite Graphs is Equivalent to Testing Graph Isomorphism
• Deterministic methods to find primes
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: Direct product primality testing of graphs is GI-hard