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

DOI10.1007/S11786-013-0156-7MaRDI QIDQ2254071zbMATH OpenOpenAlexFDO

Authors Marc Hellmuth, Wilfried Imrich, Tomas Kupka

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

approximate productCartesian productpartial star productproduct relation

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: This paper is concerned with the recognition of approximate graph products with respect to the Cartesian product. Most graphs are prime, although they can have a rich product-like structure. The proposed algorithms are based on a local approach that covers a graph by small subgraphs, so-called partial star products, and then utilizes this information to derive the global factors and an embedding of the graph under investigation into Cartesian product graphs.

Recommendations

• Approximate graph products
• Fast recognition of partial star products and quasi Cartesian products
• scientific article; zbMATH DE number 1550912
• A local prime factor decomposition algorithm
• Recognizing Cartesian products in linear time

Cites work

• A local prime factor decomposition algorithm
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Algorithm for recognizing Cartesian graph bundles
• Approximate graph products
• Arboricity and Subgraph Listing Algorithms
• Cartesian graph factorization at logarithmic cost per edge
• Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
• Factoring cartesian‐product graphs
• Graph multiplication
• scientific article; zbMATH DE number 5941289 (Why is no real title available?)
• Local algorithms for the prime factorization of strong product graphs
• On Factorable Extensions and Subgraphs of Prime Graphs
• On Isometric Embeddings of Graphs
• On recognition of strong graph bundles
• On the weak reconstruction of Cartesian-product graphs
• Recognizing Cartesian graph bundles
• Recognizing Cartesian products in linear time
• Unique square property, equitable partitions, and product-like graphs
• Weak k-reconstruction of cartesian product graphs
• Weak reconstruction of strong product graphs

Cited in

(7)

• Fibonacci \((p,r)\)-cubes as Cartesian products
• Fast recognition of partial star products and quasi Cartesian products
• Unique square property, equitable partitions, and product-like graphs
• On the Cartesian skeleton and the factorization of the strong product of digraphs
• Construction of k-matchings in graph products
• Robust Factorizations and Colorings of Tensor Graphs
• On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions

This page was built for publication: Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2254071)