论文标题
$ k $ b的最低连接边缘统治组的近似算法，具有基数约束
An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
论文作者
论文摘要
\ emph {$ k $ best Enumeration}，要求输出$ k $的解决方案而无需重复，是许多字段的数据分析的有用工具。在这样的字段中，图通常表示数据。因此，子图枚举已被极大地关注此类领域。但是，$ k $ - 最重要的枚举往往是棘手的，因为在许多情况下，找到一个最佳解决方案是\ np-hard。为了克服这个困难，我们将$ k $ b的枚举与称为\ emph {近似枚举算法}的枚举算法概念结合在一起。作为主要结果，我们提出了一种$ 4 $ - APPROXIMATION ALGORITHM，用于最小值连接的边缘统治集，该算法以$ 4 \ cdot \ opt $输出$ k $最小的解决方案，其中$ \ opt $是最低解决方案的基础$，这是\ emph {not} demph {not}的algoRithM的最低解决方案。我们提出的算法以$ \ order {nm^2δ} $延迟运行，其中$ n $，$ m $，$δ$是顶点的数量，边缘数量和输入图的最高度。
\emph{$K$-best enumeration}, which asks to output $k$-best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically represent data. Thus subgraph enumeration has been paid much attention to such fields. However, $k$-best enumeration tends to be intractable since, in many cases, finding one optimum solution is \NP-hard. To overcome this difficulty, we combine $k$-best enumeration with a concept of enumeration algorithms called \emph{approximation enumeration algorithms}. As a main result, we propose a $4$-approximation algorithm for minimal connected edge dominating sets which outputs $k$ minimal solutions with cardinality at most $4\cdot\OPT$, where $\OPT$ is the cardinality of a minimum solution which is \emph{not} outputted by the algorithm. Our proposed algorithm runs in $\order{nm^2Δ}$ delay, where $n$, $m$, $Δ$ are the number of vertices, the number of edges, and the maximum degree of an input graph.
