论文标题
上边缘统治的参数化复杂性
Parameterized Complexity of Upper Edge Domination
论文作者
论文摘要
在本文中，我们研究了经典边缘统治集（ED）问题的最大化版本，即在参数化复杂性领域中的上eds问题。在此问题中，考虑到一个无向图$ g $，一个正整数$ k $，问题是检查$ g $是否具有最小的边缘主导尺寸至少至少$ k $。我们为上EDS获得以下结果。我们证明，Upper Eds承认了一个最多$ 4K^2-2 $顶点的内核。我们还为上EDS设计了一个固定参数可拖动（FPT）算法，以$ 2^{\ MATHCAL {O}（K）} \ CDOT N^{\ MATHCAL {O} {O}（1）} $。
In this paper we study a maximization version of the classical Edge Dominating Set (EDS) problem, namely, the Upper EDS problem, in the realm of Parameterized Complexity. In this problem, given an undirected graph $G$, a positive integer $k$, the question is to check whether $G$ has a minimal edge dominating set of size at least $k$. We obtain the following results for Upper EDS. We prove that Upper EDS admits a kernel with at most $4k^2-2$ vertices. We also design a fixed-parameter tractable (FPT) algorithm for Upper EDS running in time $2^{\mathcal{O}(k)} \cdot n^{\mathcal{O}(1)}$.
