On the Cartesian skeleton and the factorization of the strong product of digraphs

DOI10.1016/J.TCS.2014.10.045MaRDI QIDQ482282zbMATH OpenOpenAlexFDO

Authors Marc Hellmuth, Tilen Marc

Publication date 22 December 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

directed graphstrong productCartesian skeletondispensableprime factor decomposition algorithms

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)

Abstract: The three standard products (the Cartesian, the direct and the strong product) of undirected graphs have been wellinvestigated, unique prime factor decomposition (PFD) are known and polynomial time algorithms have been established for determining the prime factors. For directed graphs, unique PFD results with respect to the standard products are known. However, there is still a lack of algorithms, that computes the PFD of directed graphs with respect to the direct and the strong product in general. In this contribution, we focus on the algorithmic aspects for determining the PFD of directed graphs with respect to the strong product. Essential for computing the prime factors is the construction of a so-called Cartesian skeleton. This article introduces the notion of the Cartesian skeleton of directed graphs as a generalization of the Cartesian skeleton of undirected graphs. We provide new, fast and transparent algorithms for its construction. Moreover, we present a first polynomial time algorithm for determining the PFD with respect to the strong product of arbitrary connected digraphs.

Recommendations

• A theory of Cartesian product and factorization of circulant graphs
• On Cartesian product of factor-critical graphs
• Factorization of Cartesian products of hypergraphs
• On the skew spectra of Cartesian products of graphs
• scientific article; zbMATH DE number 739124
• s-strongly perfect cartesian product of graphs
• On Cartesian skeletons of graphs
• On the gonality of Cartesian products of graphs
• Center of Cartesian and strong product of digraphs

Cites work

• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 3309924 (Why is no real title available?)
• A local prime factor decomposition algorithm
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• A survey on hypergraph products
• An efficient method for decomposition of regular structures using graph products
• Approximate graph products
• Cardinal multiplication of structures with a reflexive relation
• Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
• Factoring cardinal product graphs in polynomial time
• Factoring directed graphs with respect to the cardinal product in polynomial time
• Factoring directed graphs with respect to the cardinal product in polynomial time II
• Fast recognition of direct and strong products
• Finding the prime factors of strong direct product graphs in polynomial time
• Graph multiplication
• Handbook of product graphs
• Local algorithms for the prime factorization of strong product graphs
• On Cartesian skeletons of graphs
• Optimal analysis of structures by concepts of symmetry and regularity
• Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
• Quasi-independence, homology and the unity of type: a topological theory of characters
• Recognizing Cartesian products in linear time
• Strong products of hypergraphs: unique prime factorization theorems and algorithms
• Weak reconstruction of strong product graphs

Cited in

(12)

• Strong products of hypergraphs: unique prime factorization theorems and algorithms
• A linear-time algorithm for computing the prime decomposition of a directed graph with regard to the Cartesian product
• Digraphs products
• A local prime factor decomposition algorithm
• Asymmetric colorings of products of graphs and digraphs
• Reciprocal best match graphs
• Boundary-type sets of strong product of directed graphs
• Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
• On Cartesian skeletons of graphs
• Local algorithms for the prime factorization of strong product graphs
• Fast recognition of direct and strong products
• Best match graphs

Describes a project that uses

Uses Software

• TopoLayout

This page was built for publication: On the Cartesian skeleton and the factorization of the strong product of digraphs

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