Generating the fewest redundancy-free scheme trees from acyclic conceptual-model hypergraphs in polynomial time
作者：
Highlights：
• Generating a minimal set of redundancy-free scheme trees for a conceptual-model hypergraph is NP-hard.
• An polynomial-time algorithmic solution exists, however, if the hypergraph is acyclic.
• The algorithm ensures that the generated forest of scheme trees is redundancy-free.
• It guarantees that the generated forest of scheme trees collectively covers the information in the given conceptual-model hypergraph.
• It is guaranteed to run in polynomial time.
摘要
Highlights•Generating a minimal set of redundancy-free scheme trees for a conceptual-model hypergraph is NP-hard.•An polynomial-time algorithmic solution exists, however, if the hypergraph is acyclic.•The algorithm ensures that the generated forest of scheme trees is redundancy-free.•It guarantees that the generated forest of scheme trees collectively covers the information in the given conceptual-model hypergraph.•It is guaranteed to run in polynomial time.
论文关键词：Conceptual-model-based scheme-tree generation,Data redundancy in scheme trees,Minimal scheme-tree forests,Acyclic conceptual-model hypergraphs
论文评审过程：Received 25 June 2012, Revised 30 April 2013, Accepted 29 October 2013, Available online 16 November 2013.
论文官网地址：https://doi.org/10.1016/j.is.2013.10.009
