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.
Original language | English |
---|---|
Article number | R29 |
Journal | Electronic Journal of Combinatorics |
Volume | 15 |
Issue number | 1 R |
DOIs | |
Publication status | Published - 11 Feb 2008 |
Externally published | Yes |