Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
Date
2010
Authors
Duckworth, William
Wormald, N
Journal Title
Journal ISSN
Volume Title
Publisher
International Press
Abstract
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).
Description
Keywords
Keywords: 3-regular; Cubic; Graphs; Linear programming; Worst-case analysis
Citation
Collections
Source
Electronic Journal of Combinatorics
Type
Journal article
Book Title
Entity type
Access Statement
License Rights
DOI
Restricted until
2037-12-31
Downloads
File
Description