Skip navigation
Skip navigation

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

Howe, Stephen

Description

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.

CollectionsANU Research Publications
Date published: 2008
Type: Journal article
URI: http://hdl.handle.net/1885/17285
Source: Electronic Journal of Combinatorics

Download

File Description SizeFormat Image
01_Howe_Dominating_sets_of_random_2-in_2008.pdf188.74 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  12 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator