Geodesic
Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
The electronic journal of combinatorics, Tome 17 (2010)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We introduce a technique using linear programming that may be used to analyse the worst-case performance of a class of greedy heuristics for certain optimisation problems on regular graphs. We demonstrate the use of this technique on heuristics for bounding the size of a minimum maximal matching (MMM), a minimum connected dominating set (MCDS) and a minimum independent dominating set (MIDS) in cubic graphs. We show that for $n$-vertex connected cubic graphs, the size of an MMM is at most $9n/20+O(1)$, which is a new result. We also show that the size of an MCDS is at most $3n/4+O(1)$ and the size of a MIDS is at most $29n/70+O(1)$. These results are not new, but earlier proofs involved rather long ad-hoc arguments. By contrast, our method is to a large extent automatic and can apply to other problems as well. We also consider $n$-vertex connected cubic graphs of girth at least 5 and for such graphs we show that the size of an MMM is at most $3n/7+O(1)$, the size of an MCDS is at most $2n/3+O(1)$ and the size of a MIDS is at most $3n/8+O(1)$.
DOI : 10.37236/449
Classification : 05C85, 90C10
Mots-clés : worst-case analysis, cubic, 3-regular, graphs, linear programming 
@article{10_37236_449,
     author = {W. Duckworth and N. Wormald},
     title = {Linear programming and the worst-case analysis of greedy algorithms on cubic graphs},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/449},
     zbl = {1204.05090},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/449/}
}
TY  - JOUR
AU  - W. Duckworth
AU  - N. Wormald
TI  - Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/449/
DO  - 10.37236/449
ID  - 10_37236_449
ER  - 
%0 Journal Article
%A W. Duckworth
%A N. Wormald
%T Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/449/
%R 10.37236/449
%F 10_37236_449
W. Duckworth; N. Wormald. Linear programming and the worst-case analysis of greedy algorithms on cubic graphs. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/449

Cité par Sources :