Geodesic
Dominating sets of random 2-in 2-out directed graphs
The electronic journal of combinatorics, Tome 15 (2008)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
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$.
DOI : 10.37236/753
Classification : 05C69, 05C80, 05C20, 05C85
Mots-clés : small dominating sets, 2-in 2-out directed graphs, 2-in 2-out digraphs, deprioritised algorithm 
Stephen Howe. Dominating sets of random 2-in 2-out directed graphs. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/753
@article{10_37236_753,
     author = {Stephen Howe},
     title = {Dominating sets of random 2-in 2-out directed graphs},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/753},
     zbl = {1179.05082},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/753/}
}
TY  - JOUR
AU  - Stephen Howe
TI  - Dominating sets of random 2-in 2-out directed graphs
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/753/
DO  - 10.37236/753
ID  - 10_37236_753
ER  - 
%0 Journal Article
%A Stephen Howe
%T Dominating sets of random 2-in 2-out directed graphs
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/753/
%R 10.37236/753
%F 10_37236_753

Cité par Sources :