Linear programming and the worst-case analysis of greedy algorithms on cubic graphs

Simple item page
dc.contributor.authorDuckworth, William
dc.contributor.authorWormald, N
dc.date.accessioned2015-12-10T23:20:36Z
dc.date.issued2010
dc.date.updated2016-02-24T08:11:59Z
dc.description.abstractWe 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).
dc.identifier.issn1077-8926
dc.identifier.urihttp://hdl.handle.net/1885/66400
dc.publisherInternational Press
dc.sourceElectronic Journal of Combinatorics
dc.subjectKeywords: 3-regular; Cubic; Graphs; Linear programming; Worst-case analysis
dc.titleLinear programming and the worst-case analysis of greedy algorithms on cubic graphs
dc.typeJournal article
local.bibliographicCitation.issue1
local.bibliographicCitation.startpage29
local.contributor.affiliationDuckworth, William, College of Physical and Mathematical Sciences, ANU
local.contributor.affiliationWormald, N, University of Waterloo
local.contributor.authoremailrepository.admin@anu.edu.au
local.contributor.authoruidDuckworth, William, u4278331
local.description.embargo2037-12-31
local.description.notesImported from ARIES
local.identifier.absfor080201 - Analysis of Algorithms and Complexity
local.identifier.ariespublicationf2965xPUB1277
local.identifier.citationvolume17
local.identifier.scopusID2-s2.0-79251613715
local.identifier.uidSubmittedByf2965
local.type.statusPublished Version

Downloads

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
01_Duckworth_Linear_programming_and_the_2010.pdf
Size:
284.54 KB
Format:
Adobe Portable Document Format
Download

Collections

ANU Research Publications

DSpace software copyright © 2002-2024 LYRASIS