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

Stephen Howe

doi:10.37236/753

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

Stephen Howe^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

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	https://doi.org/10.37236/753
Publication status	Published - 11 Feb 2008
Externally published	Yes

Access to Document

10.37236/753

Cite this

@article{194c558c3cb14fbb833df0f5675b5ba7,

title = "Dominating sets of random 2-in 2-out directed graphs",

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.",

author = "Stephen Howe",

year = "2008",

month = feb,

day = "11",

doi = "10.37236/753",

language = "English",

volume = "15",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1 R",

}

TY - JOUR

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

AU - Howe, Stephen

PY - 2008/2/11

Y1 - 2008/2/11

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/39649086038

U2 - 10.37236/753

DO - 10.37236/753

M3 - Article

SN - 1077-8926

VL - 15

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1 R

M1 - R29

ER -

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

Abstract

Access to Document

Other files and links

Fingerprint

Cite this