圖的k 多重支配問題

K-Tuple Domination Problem on Graphs

黃智沂(Abner Chih Yi Huang)

指導教授 ： 唐傳義

國立清華大學/電機資訊學院/資訊工程學系/碩士(2007年)

https://doi.org/10.6843/NTHU.2007.00390

摘要

支配問題在圖形演算法上是很有名的問題， k 多重支配問題 就是其延伸。這個問題要求圖上的一個點不只要被一個點給支配，而是要被 k 個點支配。

針對樹的最小權值 k 多重支配問題，，拙作給了一個線性時間的演算法。針對平面圖，也證明其屬於 NP 完備集，此外也指出該證明之技巧不只對平面圖有用，還有很多圖類也可以被應用。

關鍵字

圖論 ； 演算法 ； 支配 ； k多重支配 ； 計算理論

並列摘要

In a graph $G(V,E)$, a vertex $v$ dominates a vertex $u$ if $u=v$ or there is an edge from $v$ to $u$. A dominating set of $G$ is a subset $D$ of $V$ such that every vertex in $V$ is dominated by at least one vertex in $D$. Domination problem, that is proposed by K{"o}nig, and its variations have fruitful literature more than $300$ publications. One class of those interesting variations is the {it multiple domination problems}, i.e., each vertex in $V$ requires to be dominated by more than one vertex in $D$. In this thesis, we study the $k$-tuple domination problem on several graph classes. We give a linear time algorithm of weighted $k$-tuple domination problem, and prove NP-completeness of $k$-tuple domination problem on some graph classes like planar graphs.

並列關鍵字

Graph Theory ； Algrotihmics ； Domination ； k-tuple Domination ； Computational Complexity

參考文獻

ematics, SIAM, Philadelphia, PA, 1988, pp. 189{199.

[4] R. Diestel, Graph Theory, vol. 173 of Graduate Texts in Mathematics,

Springer-Verlag, Heidelberg, 2005.

tween integer and fractional parameters of graphs, in: Graph theory, com-

[6] J. F. Fink, M. S. Jacobson, n-Domination in graphs, John Wiley & Sons,