论文标题
列举非余生的森林
Enumeration of Irredundant Forests
论文作者
论文摘要
反向搜索是列举结构化对象的方便方法，可以既可以用来解决理论问题并解决数据挖掘问题。该方法已经成功开发出来处理无序的树。如果文献提出了列举树木单人群的解决方案，我们在本文中研究了一个更普遍的问题，即对树木的列举 - 森林。具体来说，我们主要研究不繁殖的森林，即没有树是另一个的子树。通过将每个这样的森林压缩到有向的无环图（DAG）中，我们开发了一种反向搜索，例如枚举dag，以压缩不繁殖的森林。值得注意的是，我们证明了这些DAG与Row-Fishburn矩阵（一类精心研究的组合物体）进行了培养。在第二步中，我们得出了不冗余的森林列举，以提供解决相关问题的算法：（i）以其经典意义（允许冗余）列举森林； （ii）对森林的“亚福特”的枚举，以及（iii）频繁的“亚福特”采矿问题。本文介绍的所有方法都列举了每个项目的独特性，直到同构。
Reverse search is a convenient method for enumerating structured objects, that can be used both to address theoretical issues and to solve data mining problems. This method has already been successfully developed to handle unordered trees. If the literature proposes solutions to enumerate singletons of trees, we study in this article a more general problem, the enumeration of sets of trees -- forests. Specifically, we mainly study irredundant forests, i.e., where no tree is a subtree of another. By compressing each such forest into a Directed Acyclic Graph (DAG), we develop a reverse search like method to enumerate DAGs compressing irredundant forests. Remarkably, we prove that these DAGs are in bijection with the row-Fishburn matrices, a well-studied class of combinatorial objects. In a second step, we derive our irredundant forest enumeration to provide algorithms for tackling related problems: (i) enumeration of forests in their classical sense (where redundancy is allowed); (ii) the enumeration of "subforests" of a forest, and (iii) the frequent "subforest" mining problem. All the methods presented in this article enumerate each item uniquely, up to isomorphism.
