Dominating sets of random 2-in 2-out directed graphs
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.
Collections | ANU Research Publications |
---|---|
Date published: | 2008 |
Type: | Journal article |
URI: | http://hdl.handle.net/1885/17285 |
Source: | Electronic Journal of Combinatorics |
Download
File | Description | Size | Format | Image |
---|---|---|---|---|
01_Howe_Dominating_sets_of_random_2-in_2008.pdf | 188.74 kB | Adobe PDF | Request a copy |
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.
Updated: 17 November 2022/ Responsible Officer: University Librarian/ Page Contact: Library Systems & Web Coordinator