Dominating sets of random 2-in 2-out directed graphs
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|
|Source:||Electronic Journal of Combinatorics|
|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.