Skip navigation
Skip navigation

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

Duckworth, William; Wormald, N

Description

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
URI: http://hdl.handle.net/1885/66400
Source: Electronic Journal of Combinatorics

Download

File Description SizeFormat Image
01_Duckworth_Linear_programming_and_the_2010.pdf284.54 kBAdobe PDF    Request a copy


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

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator