Algorithmic aspect of k-tuple domination in graphs

檔案

本條目沒有附加檔案。

日期

2002-09-01

期刊名稱

TAIWANESE JOURNAL OF MATHEMATICS

摘要

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset such that every vertex in the graph is dominated by at least k vertices in this set. The present paper studies the k-tuple domination problem in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the 2-tuple domination problem in trees by employing a labeling method.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料