Dominating sets in directed graphs

There are no files associated with this record.

Title Dominating sets in directed graphs
Author Pang, Chaoyi; Zhang, Rui; Zhang, Qing; Wang, Junhu
Journal Name Information Sciences
Year Published 2010
Place of publication United States
Publisher Elsevier
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.
Peer Reviewed Yes
Published Yes
Alternative URI http://dx.doi.org/10.1016/j.ins.2010.06.009
Volume 180
Issue Number 19
Page from 3647
Page to 3652
ISSN 0020-0255
Date Accessioned 2011-01-25
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Database Management
URI http://hdl.handle.net/10072/36135
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice