Recognizing Cartesian products in linear time
DOI10.1016/J.DISC.2005.09.038zbMATH Open1111.05081OpenAlexW2127749196WikidataQ56688309 ScholiaQ56688309MaRDI QIDQ864136FDOQ864136
Authors: Wilfried Imrich, Iztok Peterin 
Publication date: 13 February 2007
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2005.09.038
Recommendations
- Generalized line graphs: Cartesian products and complexity of recognition
- Recognizing Cartesian products of matrices and polytopes
- Fast searching on Cartesian products of graphs
- Fast recognition of partial star products and quasi Cartesian products
- Recognizing triangulated Cartesian graph products
- The fast search number of a Cartesian product of graphs
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
- Fast recognition of direct and strong products
- scientific article; zbMATH DE number 125862
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cites Work
- Title not available (Why is that?)
- Graph multiplication
- SOME UNSOLVED PROBLEMS IN GRAPH THEORY
- Cartesian graph factorization at logarithmic cost per edge
- Title not available (Why is that?)
- 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
Cited In (36)
- Factoring a graph in polynomial time
- A note on Winkler's algorithm for factoring a connected graph
- DP‐coloring Cartesian products of graphs
- Epistatic arithmetic crossover based on Cartesian graph product in ensemble differential evolution
- Treetopes and their graphs
- Bandwidth and pathwidth of three-dimensional grids
- Approximate graph products
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Tree 3-spanners on generalized prisms of graphs
- Average running time analysis of an algorithm to calculate the size of the union of Cartesian products.
- Fast recognition of direct and strong products
- The pre-hull number and lexicographic product
- Distance formula for direct-co-direct product in the case of disconnected factors
- Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
- Cartesian graph factorization at logarithmic cost per edge
- ON THE EDGE-CONNECTIVITY OF CARTESIAN PRODUCT GRAPHS
- Fast recognition of partial star products and quasi Cartesian products
- On Cartesian products of signed graphs
- Robust Factorizations and Colorings of Tensor Graphs
- Systematic and deterministic graph minor embedding for Cartesian products of graphs
- Factorization and pseudofactorization of weighted graphs
- On the Cartesian skeleton and the factorization of the strong product of digraphs
- Connectivity for some families of composition networks
- Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
- On some metric properties of direct-co-direct product
- Product graph representations
- On the Colin de Verdière numbers of Cartesian graph products
- Fast factorization of Cartesian products of (directed) hypergraphs
- On distance and strong metric dimension of the modular product
- A linear-time algorithm for computing the prime decomposition of a directed graph with regard to the Cartesian product
- On the complexity of recognizing \(S\)-composite and \(S\)-prime graphs
- The arc-types of Cayley graphs
- Recognizing triangulated Cartesian graph products
- Cartesian products of directed graphs with loops
- A survey on hypergraph products
- Recognizing some complementary products
This page was built for publication: Recognizing Cartesian products in linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q864136)
