论文标题
多项式 - 列表枚举算法的设计
Design of Polynomial-delay Enumeration Algorithms in Transitive Systems
论文作者
论文摘要
在本文中，作为一个新概念，我们将传递系统定义为设置系统$（v，{\ Mathcal c} \ subseteq 2^v）$在有限的元素$ v $上，以使每三个套装$ x，y，z \ in {\ natercal c} $ in {\ sebseteq x y $ cap y $ cap y $ c} $，我们在{\ Mathcal c} $ a组件中调用set $ c \。 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 $。我们证明，存在着一种列出的算法，这些算法以多项式相对于输入大小和甲状管的运行时间限制的所有解决方案。 The proposed algorithm yields the first polynomial-delay algorithms for enumerating connectors in an attributed graph and for enumerating all subgraphs with various types of connectivities such as all $k$-edge/vertex-connected induced subgraphs and all $k$-edge/vertex-connected spanning subgraphs in a given undirected/directed graph for a fixed $k$.
In this paper, as a new notion, we define a transitive system to be a set system $(V, {\mathcal C}\subseteq 2^V)$ on a finite set $V$ of elements such that every three sets $X,Y,Z\in{\mathcal C}$ with $Z\subseteq X\cap Y$ implies $X\cup Y\in{\mathcal C}$, 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 in delay bounded by a polynomial with respect to the input size and the running times of the oracles. The proposed algorithm yields the first polynomial-delay algorithms for enumerating connectors in an attributed graph and for enumerating all subgraphs with various types of connectivities such as all $k$-edge/vertex-connected induced subgraphs and all $k$-edge/vertex-connected spanning subgraphs in a given undirected/directed graph for a fixed $k$.
