Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs

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

zbMATH Keywords

Cartesian productapproximate productpartial star productproduct relation

Mathematics Subject Classification ID

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