Skip navigation
Skip navigation

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

Duckworth, William; Wormald, N


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...[Show more]

CollectionsANU Research Publications
Date published: 2010
Type: Journal article
Source: Electronic Journal of Combinatorics


File Description SizeFormat Image
01_Duckworth_Linear_programming_and_the_2010.pdf284.54 kBAdobe PDFThumbnail

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  17 November 2022/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator