Factoring a graph in polynomial time
From MaRDI portal
Publication:579285
DOI10.1016/S0195-6698(87)80012-4zbMATH Open0625.05050MaRDI QIDQ579285FDOQ579285
Publication date: 1987
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Recommendations
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Factoring cardinal product graphs in polynomial time
- Recognizing Cartesian products in linear time
- Finding the prime factors of strong direct product graphs in polynomial time
- Cartesian graph factorization at logarithmic cost per edge
Cites Work
Cited In (32)
- On Cartesian skeletons of graphs
- A note on Winkler's algorithm for factoring a connected graph
- Computing equivalence classes among the edges of a graph with applications
- Recognizing graph products and bundles
- Recognizing Cartesian products in linear time
- Direct product primality testing of graphs is GI-hard
- On recognition of strong graph bundles
- Strict refinement for graphs and digraphs
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Recognizing Cartesian graph bundles
- Factoring directed graphs with respect to the cardinal product in polynomial time II
- Algorithm for recognizing Cartesian graph bundles
- Factoring directed graphs with respect to the cardinal product in polynomial time
- Factoring cardinal product graphs in polynomial time
- Finding the prime factors of strong direct product graphs in polynomial time
- Strong products of \(\chi\)-critical graphs
- On some graph operations and related applications
- Cartesian graph factorization at logarithmic cost per edge
- On Cartesian products of signed graphs
- Robust Factorizations and Colorings of Tensor Graphs
- On the complexity of the embedding problem for hypercube related graphs
- Factorization and pseudofactorization of weighted graphs
- Strong products of Kneser graphs
- Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
- Unique prime Cartesian factorization of graphs over finite fields
- The complement of the Djoković-Winkler relation
- Product graph representations
- Factoring Boolean functions using graph partitioning
- Fast factorization of Cartesian products of (directed) hypergraphs
- Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
- Factoring cartesian‐product graphs
- Recognizing some complementary products
This page was built for publication: Factoring a graph in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q579285)
