Dominating sets of random 2-in 2-out directed graphs

dc.contributor.author	Howe, Stephen
dc.date.accessioned	2015-12-07T22:14:06Z
dc.date.issued	2008
dc.date.updated	2015-12-07T07:23:40Z
dc.description.abstract	We analyse an algorithm for finding small dominating sets of 2-in 2-out directed graphs using a deprioritised algorithm and differential equations. This deprioritised approach determines an a.a.s. upper bound of 0.39856n on the size of the smallest dominating set of a random 2-in 2-out digraph on n vertices. Direct expectation arguments determine a corresponding lower bound of 0.3495n.
dc.identifier.issn	1077-8926
dc.identifier.uri	http://hdl.handle.net/1885/17285
dc.publisher	International Press
dc.source	Electronic Journal of Combinatorics
dc.title	Dominating sets of random 2-in 2-out directed graphs
dc.type	Journal article
local.bibliographicCitation.issue	1
local.bibliographicCitation.startpage	#R29
local.contributor.affiliation	Howe, Stephen, College of Physical and Mathematical Sciences, ANU
local.contributor.authoruid	Howe, Stephen, u4688178
local.description.embargo	2037-12-31
local.description.notes	Imported from ARIES
local.identifier.absfor	010104 - Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)
local.identifier.ariespublication	u4379881xPUB1
local.identifier.citationvolume	15
local.identifier.scopusID	2-s2.0-39649086038
local.type.status	Published Version

Downloads

Now showing 1 - 1 of 1