On the Cartesian skeleton and the factorization of the strong product of digraphs
From MaRDI portal
Publication:482282
DOI10.1016/J.TCS.2014.10.045zbMATH Open1315.05135arXiv1401.4965OpenAlexW1978416015MaRDI QIDQ482282FDOQ482282
Authors: Marc Hellmuth, Tilen Marc 
Publication date: 22 December 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1401.4965
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
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)
Cites Work
- Handbook of product graphs
- Title not available (Why is that?)
- Graph multiplication
- Factoring cardinal product graphs in polynomial time
- On Cartesian skeletons of graphs
- Finding the prime factors of strong direct product graphs in polynomial time
- A survey on hypergraph products
- Strong products of hypergraphs: unique prime factorization theorems and algorithms
- Optimal analysis of structures by concepts of symmetry and regularity
- An efficient method for decomposition of regular structures using graph products
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Recognizing Cartesian products in linear time
- Approximate graph products
- Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
- A local prime factor decomposition algorithm
- Local algorithms for the prime factorization of strong product graphs
- Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
- Quasi-independence, homology and the unity of type: a topological theory of characters
- Fast recognition of direct and strong products
- Factoring directed graphs with respect to the cardinal product in polynomial time II
- Factoring directed graphs with respect to the cardinal product in polynomial time
- Title not available (Why is that?)
- Cardinal multiplication of structures with a reflexive relation
- Weak reconstruction of strong product graphs
Cited In (12)
- On Cartesian skeletons of graphs
- A local prime factor decomposition algorithm
- Local algorithms for the prime factorization of strong product graphs
- Strong products of hypergraphs: unique prime factorization theorems and algorithms
- Fast recognition of direct and strong products
- Asymmetric colorings of products of graphs and digraphs
- Best match graphs
- Digraphs Products
- Reciprocal best match graphs
- Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
- Boundary-type sets of strong product of directed graphs
- A linear-time algorithm for computing the prime decomposition of a directed graph with regard to the Cartesian product
Uses Software
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)
