Show simple item record

dc.contributor.authorPang, Chaoyi
dc.contributor.authorZhang, Rui
dc.contributor.authorZhang, Qing
dc.contributor.authorWang, Junhu
dc.date.accessioned2017-05-03T14:22:31Z
dc.date.available2017-05-03T14:22:31Z
dc.date.issued2010
dc.date.modified2011-02-14T09:12:26Z
dc.identifier.issn0020-0255
dc.identifier.doi10.1016/j.ins.2010.06.009
dc.identifier.urihttp://hdl.handle.net/10072/36135
dc.description.abstractWe 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.peerreviewedYes
dc.description.publicationstatusYes
dc.languageEnglish
dc.language.isoeng
dc.publisherElsevier
dc.publisher.placeUnited States
dc.relation.ispartofstudentpublicationN
dc.relation.ispartofpagefrom3647
dc.relation.ispartofpageto3652
dc.relation.ispartofissue19
dc.relation.ispartofjournalInformation Sciences
dc.relation.ispartofvolume180
dc.rights.retentionY
dc.subject.fieldofresearchMathematical sciences
dc.subject.fieldofresearchInformation and computing sciences
dc.subject.fieldofresearchDatabase systems
dc.subject.fieldofresearchEngineering
dc.subject.fieldofresearchcode49
dc.subject.fieldofresearchcode46
dc.subject.fieldofresearchcode460505
dc.subject.fieldofresearchcode40
dc.titleDominating sets in directed graphs
dc.typeJournal article
dc.type.descriptionC1 - Articles
dc.type.codeC - Journal Articles
gro.date.issued2010
gro.hasfulltextNo Full Text
gro.griffith.authorWang, John


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

  • Journal articles
    Contains articles published by Griffith authors in scholarly journals.

Show simple item record