Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
From MaRDI portal
Publication:2254071
DOI10.1007/s11786-013-0156-7zbMath1319.68157arXiv1303.6803OpenAlexW3100644252MaRDI QIDQ2254071
Tomas Kupka, Marc Hellmuth, Wilfried Imrich
Publication date: 4 February 2015
Published in: Mathematics in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1303.6803
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)
Related Items
Construction of k-matchings in graph products, Unique square property, equitable partitions, and product-like graphs, Robust Factorizations and Colorings of Tensor Graphs, Fibonacci \((p,r)\)-cubes as Cartesian products, On the Cartesian skeleton and the factorization of the strong product of digraphs, On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
Cites Work
- Unnamed Item
- Unnamed Item
- Unique square property, equitable partitions, and product-like graphs
- A local prime factor decomposition algorithm
- Local algorithms for the prime factorization of strong product graphs
- Graph multiplication
- Recognizing Cartesian products in linear time
- Weak reconstruction of strong product graphs
- Approximate graph products
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
- Cartesian graph factorization at logarithmic cost per edge
- Recognizing Cartesian graph bundles
- Algorithm for recognizing Cartesian graph bundles
- On the weak reconstruction of Cartesian-product graphs
- Weak k-reconstruction of cartesian product graphs
- Arboricity and Subgraph Listing Algorithms
- On Isometric Embeddings of Graphs
- Factoring cartesian‐product graphs
- On Factorable Extensions and Subgraphs of Prime Graphs