Paper Info
Title
Polynomial Delay And Space Discovery Of Connected And Acyclic Sub-Hypergraphs In A Hypergraph
Abstract
In this paper, we study the problem of finding all tree-like substructure contained in a hypergraph, with potential applications to substructure mining from relational data. We employ the class of connected and Berge acyclic sub-hypergraphs as definition of tree-like substructures, which is the most restricted notion of acyclicities for hypergraphs. Then, we present an efficient depth-first algorithm that finds all connected and Berge acyclic sub-hypergraphs S in a hypergraph H with m hyperedges and n vertices in O(nm(2)) time per solution (delay) using O(N) space, where N = parallel to H parallel to is the total input size. To achieve efficient enumeration, we use the notion of the maximum border set. This result gives the first polynomial delay and time algorithm for enumeration of connected and Berge-acyclic sub-hypergraphs. We also present an incremental enumeration algorithm that finds all solutions S in O(Delta MB(S)tau(m)) = O(rd .tau (m)) delay using O(N) space and preprocessing, whose delay depends only on the difference of solutions, where S is the enumerated sub-hypergraph, Delta MB(S) is the number of newly added hyperedges to the maximum border of S, r and d are the rank and degree of H, respectively, and tau(m) = ((log logm)(2)/log log logm).
Year
DOI
Venue
2013
10.1007/978-3-642-40897-7_21
DISCOVERY SCIENCE
Field
DocType
Volume
Polynomial,Hypergraph,PSPACE,Artificial intelligence,Enumeration algorithm,Log-log plot,Discrete mathematics,Combinatorics,Vertex (geometry),Constraint graph,Enumeration,Mathematics,Machine learning
Conference
8140
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
25
4
Name
Order
Citations
PageRank
Kunihiro Wasa11310.85
Takeaki Uno21319107.99
Kouichi Hirata313032.04
Hiroki Arimura4113092.90