论文标题
设定系统中的多项式 - 列表枚举算法
Polynomial-delay Enumeration Algorithms in Set Systems
论文作者
论文摘要
我们考虑一个设置系统$（v，{\ Mathcal C} \ subseteq 2^v）$上的元素的$ v $，我们在{\ Mathcal c} $中称为set $ c \ in component。 We assume that two oracles $\mathrm{L}_1$ and $\mathrm{L}_2$ are available, where given two subsets $X,Y\subseteq V$, $\mathrm{L}_1$ returns a maximal component $C\in {\mathcal C}$ with $X\subseteq C\subseteq Y$;并给定一个$ y \ subseteq v $，$ \ mathrm {l} _2 $带有$ c \ subseteq y $ in {\ mathcal c} $ in {\ mathcal c} $中的所有最大组件$ c \。给定一个属性的集合$ i $和一个函数$σ：v \至2^i $在及传递系统中，如果{\ mathcal c} $ in {\ mathcal c} $中的组件$ c \如果$ c $中的一组common属性集合为最大值，则称为解决方案；即$ \ bigcap_ {v \ in C}σ（v）\ supsetneq \ bigcap_ {v \ in x}σ（v）$ x \ in {\ Mathcal c} $ in {\ Mathcal c} $，带有$ C \ subsetneq x $。我们证明，存在通过多项式相对于输入尺寸和甲状管的运行时间限制的所有解决方案（或所有组件）列举所有解决方案（或所有组件）的算法。
We consider a set system $(V, {\mathcal C}\subseteq 2^V)$ on a finite set $V$ of elements, where we call a set $C\in {\mathcal C}$ a component. We assume that two oracles $\mathrm{L}_1$ and $\mathrm{L}_2$ are available, where given two subsets $X,Y\subseteq V$, $\mathrm{L}_1$ returns a maximal component $C\in {\mathcal C}$ with $X\subseteq C\subseteq Y$; and given a set $Y\subseteq V$, $\mathrm{L}_2$ returns all maximal components $C\in {\mathcal C}$ with $C\subseteq Y$. Given a set $I$ of attributes and a function $σ:V\to 2^I$ in a transitive system, a component $C\in {\mathcal C}$ is called a solution if the set of common attributes in $C$ is inclusively maximal; i.e., $\bigcap_{v\in C}σ(v)\supsetneq \bigcap_{v\in X}σ(v)$ for any component $X\in{\mathcal C}$ with $C\subsetneq X$. We prove that there exists an algorithm of enumerating all solutions (or all components) in delay bounded by a polynomial with respect to the input size and the running times of the oracles.
