Fast factorization of Cartesian products of (directed) hypergraphs

DOI10.1016/J.TCS.2015.11.038MaRDI QIDQ906379zbMATH OpenOpenAlexFDO

Authors Marc Hellmuth, Florian Lehner

Publication date 21 January 2016

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

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

zbMATH Keywords

Cartesian productfactorization algorithmprime factor decompositiondirected hypergraph2-section

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Cartesian products of graphs and hypergraphs have been studied since the 1960s. For (un)directed hypergraphs, unique emph{prime factor decomposition (PFD)} results with respect to the Cartesian product are known. However, there is still a lack of algorithms, that compute the PFD of directed hypergraphs with respect to the Cartesian product. In this contribution, we focus on the algorithmic aspects for determining the Cartesian prime factors of a finite, connected, directed hypergraph and present a first polynomial time algorithm to compute its PFD. In particular, the algorithm has time complexity $O(|E||V|r^2)$ for hypergraphs $H=(V,E)$, where the rank $r$ is the maximum number of vertices contained in an hyperedge of $H$. If $r$ is bounded, then this algorithm performs even in $O(|E|lo{g}^2(|V|))$ time. Thus, our method additionally improves also the time complexity of PFD-algorithms designed for undirected hypergraphs that have time complexity $O(|E||V|r^{6}Delt{a}^6)$, where $Delta$ is the maximum number of hyperedges a vertex is contained in.

Recommendations

• Factorization of Cartesian products of hypergraphs
• Factorization of products of hypergraphs: Structure and algorithms
• Factoring directed graphs with respect to the cardinal product in polynomial time
• The fast search number of a Cartesian product of graphs
• Factoring directed graphs with respect to the cardinal product in polynomial time II
• Fast searching on Cartesian products of graphs
• Factoring cardinal product graphs in polynomial time
• Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
• Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
• On Cartesian product of factor-critical graphs

Cites work

• scientific article; zbMATH DE number 3754749 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 165094 (Why is no real title available?)
• scientific article; zbMATH DE number 4114686 (Why is no real title available?)
• scientific article; zbMATH DE number 5064049 (Why is no real title available?)
• scientific article; zbMATH DE number 3246262 (Why is no real title available?)
• scientific article; zbMATH DE number 3308993 (Why is no real title available?)
• A linear-time algorithm for computing the prime decomposition of a directed graph with regard to the Cartesian product
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• A survey on hypergraph products
• Cartesian graph factorization at logarithmic cost per edge
• Diagonalized Cartesian products of \(S\)-prime graphs are \(S\)-prime
• Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
• Factoring a graph in polynomial time
• Factorization of products of hypergraphs: Structure and algorithms
• Graph multiplication
• Handbook of product graphs
• Hypergraph theory. An introduction
• Monotone properties of \(k\)-uniform hypergraphs are weakly evasive
• On subgraphs of Cartesian product graphs
• On subgraphs of Cartesian product graphs and S-primeness
• On the complexity of recognizing S-composite and S-prime graphs
• Product graph representations
• Recognizing Cartesian products in linear time
• Remarks on the Cartesian product of two graphs
• Strong products of hypergraphs: unique prime factorization theorems and algorithms
• The Cartesian product of hypergraphs
• Über das schwache Kartesische Produkt von Graphen

Cited in

(11)

• Strong products of hypergraphs: unique prime factorization theorems and algorithms
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• 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
• The cut method on hypergraphs for the Wiener index
• Kronecker product of tensors and hypergraphs: structure and dynamics
• Associativity and non-associativity of some hypergraph products
• Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
• A linear-time algorithm for computing the prime decomposition of a directed graph with regard to the Cartesian product
• Factorization of products of hypergraphs: Structure and algorithms
• Factorization of Cartesian products of hypergraphs

This page was built for publication: Fast factorization of Cartesian products of (directed) hypergraphs

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