Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Linear programming and the worst-case analysis of greedy algorithms on cubic graphs. | Linear programming and the worst-case analysis of greedy algorithms on cubic graphs W. Duckworth t N. Wormald t Mathematical Sciences Institute Department of Combinatorics Optimization The Australian National University University of Waterloo Canberra ACT 0200 Australia Waterloo ON Canada N2L 3G1 nwormald@ Submitted Oct 20 2009 Accepted Jun 5 2010 Published Dec 10 2010 Mathematics Subject Classification 05C85 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 . Keywords worst-case analysis cubic 3-regular graphs linear programming. This research was mainly carried out while the authors were in the Department of Mathematics and Statistics The University of Melbourne VIC 3010 Australia. Research supported by Macquarie University while the author was supported by the Macquarie University Research Fellowships Grants Scheme. 1 Research supported by the Australian Research Council while the author was affiliated with the Department of Mathematics and Statistics The .
