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
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
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice