Recognizing Cartesian products in linear time
From MaRDI portal
Publication:864136
DOI10.1016/j.disc.2005.09.038zbMath1111.05081OpenAlexW2127749196WikidataQ56688309 ScholiaQ56688309MaRDI QIDQ864136
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
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)
Related Items
Distance formula for direct-co-direct product in the case of disconnected factors ⋮ Systematic and deterministic graph minor embedding for Cartesian products of graphs ⋮ Recognizing some complementary products ⋮ Connectivity for some families of composition networks ⋮ DP‐coloring Cartesian products of graphs ⋮ On some metric properties of direct-co-direct product ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ 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 ⋮ The pre-hull number and lexicographic product ⋮ A survey on hypergraph products ⋮ On the complexity of recognizing \(S\)-composite and \(S\)-prime graphs ⋮ ON THE EDGE-CONNECTIVITY OF CARTESIAN PRODUCT GRAPHS ⋮ Cartesian products of directed graphs with loops ⋮ The arc-types of Cayley graphs ⋮ Recognizing triangulated Cartesian graph products ⋮ On the Cartesian skeleton and the factorization of the strong product of digraphs ⋮ Epistatic arithmetic crossover based on Cartesian graph product in ensemble differential evolution ⋮ On Cartesian products of signed graphs ⋮ Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs ⋮ Bandwidth and pathwidth of three-dimensional grids ⋮ Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time ⋮ Approximate graph products ⋮ On the Colin de Verdière numbers of Cartesian graph products
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Factoring a graph in polynomial time
- Graph multiplication
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Cartesian graph factorization at logarithmic cost per edge
- Product graph representations
- SOME UNSOLVED PROBLEMS IN GRAPH THEORY
