Fast recognition of partial star products and quasi Cartesian products

DOI10.26493/1855-3974.520.933zbMATH Open1329.05108arXiv1308.2101OpenAlexW1899017421WikidataQ129355303 ScholiaQ129355303MaRDI QIDQ3465660FDOQ3465660

Authors: Marc Hellmuth, Wilfried Imrich, Tomas Kupka 

Publication date: 22 January 2016

Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)

Abstract: This paper is concerned with the fast computation of a relation $R$ on the edge set of connected graphs that plays a decisive role in the recognition of approximate Cartesian products, the weak reconstruction of Cartesian products, and the recognition of Cartesian graph bundles with a triangle free basis. A special case of $R$ is the relation $delt{a}^{a}st$, whose convex closure yields the product relation $sigma$ that induces the prime factor decomposition of connected graphs with respect to the Cartesian product. For the construction of $R$ so-called Partial Star Products are of particular interest. Several special data structures are used that allow to compute Partial Star Products in constant time. These computations are tuned to the recognition of approximate graph products, but also lead to a linear time algorithm for the computation of $delt{a}^{a}st$ for graphs with maximum bounded degree. Furthermore, we define emph{quasi Cartesian products} as graphs with non-trivial $delt{a}^{a}st$. We provide several examples, and show that quasi Cartesian products can be recognized in linear time for graphs with bounded maximum degree. Finally, we note that quasi products can be recognized in sublinear time with a parallelized algorithm.

Full work available at URL: https://arxiv.org/abs/1308.2101

Recommendations

• Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
• Recognizing Cartesian products in linear time
• Fast recognition of direct and strong products
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Approximate graph products

zbMATH Keywords

Cartesian productgraph bundleapproximate productpartial star productproduct relationquasi product

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cited In (2)

• Recognizing Cartesian products in linear time
• Construction of k-matchings in graph products

This page was built for publication: Fast recognition of partial star products and quasi Cartesian products

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