A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
From MaRDI portal
Publication:1067411
DOI10.1016/0166-218X(85)90066-6zbMath0579.68028WikidataQ56688308 ScholiaQ56688308MaRDI QIDQ1067411
Joan Feigenbaum, Alejandro A. Schäffer, J. E. Hershberger
Publication date: 1985
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Algorithm for recognizing Cartesian graph bundles ⋮ Strong products of Kneser graphs ⋮ Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time ⋮ Recognizing Cartesian graph bundles ⋮ Recognizing Cartesian products in linear time ⋮ On the weak reconstruction of Cartesian-product graphs ⋮ Factoring cartesian‐product graphs ⋮ Recognizing some complementary products ⋮ Unique square property, equitable partitions, and product-like graphs ⋮ Unnamed Item ⋮ Factorization and pseudofactorization of weighted graphs ⋮ Treetopes and their graphs ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ Fast factorization of Cartesian products of (directed) hypergraphs ⋮ Cartesian products of directed graphs with loops ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ On the Cartesian skeleton and the factorization of the strong product of digraphs ⋮ On Cartesian products of signed graphs ⋮ Arithmetic for rooted trees ⋮ Computing equivalence classes among the edges of a graph with applications ⋮ Finding the prime factors of strong direct product graphs in polynomial time ⋮ A note on Winkler's algorithm for factoring a connected graph ⋮ An algorithm forK-convex closure and an application ⋮ Direct product primality testing of graphs is GI-hard ⋮ Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs ⋮ Cartesian graph factorization at logarithmic cost per edge ⋮ Factoring a graph in polynomial time ⋮ Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time ⋮ Strong products of \(\chi\)-critical graphs ⋮ On the complexity of the embedding problem for hypercube related graphs ⋮ Approximate graph products ⋮ On Some Graph Operations and Related Applications ⋮ Factoring cardinal product graphs in polynomial time ⋮ The grid property and product-like hypergraphs ⋮ Strict refinement for graphs and digraphs
Uses Software
Cites Work
