论文标题
在图中安全连接支配的算法方面
Algorithmic Aspects of Secure Connected Domination in Graphs
论文作者
论文摘要
令$ g =（v，e）$为一个简单，无向和连接的图。连接的统治集$ s \ subseteq v $是$ g $的安全连接的托管组，如果对于v \ setminus s $中的每个$ u \，则在s $中存在$ v \ in s $，以至于$（u，v）\ in E $ in e $ and set $（s \ setMinus \ \ \ \ \ \ {v \ {v \} $ a $由$γ_{sc}（g）$表示的安全连接的$ g $的$ g $的最小尺寸称为$ g $的安全连接支配数。鉴于图$ g $和一个正整数$ k，$ $ secure Connected Dointion（SCDM）问题是检查$ G $在本文中是否具有最多$k。$的安全连接的主导组合集，我们证明SCDM问题是Doubly Chordal Graphs的NP-Complete，它是Chordal Graphers的Doubly-Conterte。我们研究了两分图的某些子类的复杂性，即恒星凸两分部分，梳子凸双方，弦弦两分和链图。最小安全连接的主导集（MSCD）问题是在输入图中找到一个安全连接的最小尺寸的主导集。我们提出了MSCDS的$（δ（g）+1）$ - 近似算法，其中$δ（g）$是输入图$ g $的最大程度，并证明MSCD在$（1-ε）ln（| v |）$中均无法近似于任何$ε> 0 $ NP $ NP \ subseteq dime | vib | v | v | v | v | v | v |两部分图。最后，我们证明MSCD为$δ（g）= 4 $的图形是APX算法。
Let $G = (V,E)$ be a simple, undirected and connected graph. A connected dominating set $S \subseteq V$ is a secure connected dominating set of $G$, if for each $ u \in V\setminus S$, there exists $v\in S$ such that $(u,v) \in E$ and the set $(S \setminus \{ v \}) \cup \{ u \} $ is a connected dominating set of $G$. The minimum size of a secure connected dominating set of $G$ denoted by $ γ_{sc} (G)$, is called the secure connected domination number of $G$. Given a graph $ G$ and a positive integer $ k,$ the Secure Connected Domination (SCDM) problem is to check whether $ G $ has a secure connected dominating set of size at most $ k.$ In this paper, we prove that the SCDM problem is NP-complete for doubly chordal graphs, a subclass of chordal graphs. We investigate the complexity of this problem for some subclasses of bipartite graphs namely, star convex bipartite, comb convex bipartite, chordal bipartite and chain graphs. The Minimum Secure Connected Dominating Set (MSCDS) problem is to find a secure connected dominating set of minimum size in the input graph. We propose a $ (Δ(G)+1) $ - approximation algorithm for MSCDS, where $ Δ(G) $ is the maximum degree of the input graph $ G $ and prove that MSCDS cannot be approximated within $ (1 -ε) ln(| V |)$ for any $ ε> 0 $ unless $ NP \subseteq DTIME(| V |^{O(log log | V |)})$ even for bipartite graphs. Finally, we show that the MSCDS is APX-complete for graphs with $Δ(G)=4$.
