Geodesic
Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
The electronic journal of combinatorics, Tome 17 (2010)

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

Zbl EuDML
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 
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
@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

Cité par Sources :