1. Dominating sets in directed graphs
- Author
-
Pang, Chaoyi, Zhang, Rui, Zhang, Qing, and Wang, Junhu
- Subjects
- *
GRAPHIC methods , *DOMINATING set , *DIRECTED graphs , *GRAPH theory , *SET theory , *COMPUTER engineering , *COMPUTER networks , *COMPUTER science - Abstract
Abstract: We consider the problem of incrementally computing a minimal dominating set of a directed graph after the insertion or deletion of a set of arcs. Earlier results have either focused on the study of the properties that minimum (not minimal) dominating sets preserved or lacked to investigate which update affects a minimal dominating set and in what ways. In this paper, we first show how to incrementally compute a minimal dominating set on arc insertions. We then reduce the case of computing a minimal dominating set on arc deletions to the case of insertions. Some properties on minimal dominating sets are provided to support the incremental strategy. Lastly, we give a new bound on the size of minimum dominating sets based on those results. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF