Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875978 | Theoretical Computer Science | 2016 | 11 Pages |
Abstract
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|r2) for hypergraphs H=(V,E), where the rank r is the maximum number of vertices contained in a hyperedge of H. If r is bounded, then this algorithm performs even in O(|E|log2â¡(|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|r6Î6), where Î is the maximum number of hyperedges a vertex is contained in.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Marc Hellmuth, Florian Lehner,