Subscribe to Syndicate

Partial Star Products: A Local Covering Approach for the Recognition of Approximate Cartesian Product Graphs

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
Journal: 
Mathematics in Computer Science
Publication Date: 
12 Dec 2013
Citation: 
[HWT13] Hellmuth, M., Imrich, W., and Kupka, T.: Partial Star Products: A Local Covering Approach for the Recognition of Approximate Cartesian Product Graphs. Mathematics in Computer Science, 7(3):255-273,2013.
Researchers: