dc.contributor.author | Pang, Chaoyi | |
dc.contributor.author | Zhang, Rui | |
dc.contributor.author | Zhang, Qing | |
dc.contributor.author | Wang, Junhu | |
dc.date.accessioned | 2017-05-03T14:22:31Z | |
dc.date.available | 2017-05-03T14:22:31Z | |
dc.date.issued | 2010 | |
dc.date.modified | 2011-02-14T09:12:26Z | |
dc.identifier.issn | 0020-0255 | |
dc.identifier.doi | 10.1016/j.ins.2010.06.009 | |
dc.identifier.uri | http://hdl.handle.net/10072/36135 | |
dc.description.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. | |
dc.description.peerreviewed | Yes | |
dc.description.publicationstatus | Yes | |
dc.language | English | |
dc.language.iso | eng | |
dc.publisher | Elsevier | |
dc.publisher.place | United States | |
dc.relation.ispartofstudentpublication | N | |
dc.relation.ispartofpagefrom | 3647 | |
dc.relation.ispartofpageto | 3652 | |
dc.relation.ispartofissue | 19 | |
dc.relation.ispartofjournal | Information Sciences | |
dc.relation.ispartofvolume | 180 | |
dc.rights.retention | Y | |
dc.subject.fieldofresearch | Mathematical sciences | |
dc.subject.fieldofresearch | Information and computing sciences | |
dc.subject.fieldofresearch | Database systems | |
dc.subject.fieldofresearch | Engineering | |
dc.subject.fieldofresearchcode | 49 | |
dc.subject.fieldofresearchcode | 46 | |
dc.subject.fieldofresearchcode | 460505 | |
dc.subject.fieldofresearchcode | 40 | |
dc.title | Dominating sets in directed graphs | |
dc.type | Journal article | |
dc.type.description | C1 - Articles | |
dc.type.code | C - Journal Articles | |
gro.date.issued | 2010 | |
gro.hasfulltext | No Full Text | |
gro.griffith.author | Wang, John | |