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

zbMath1204.05090MaRDI QIDQ612969

William Duckworth, Nicholas C. Wormald

Publication date: 16 December 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/226613

zbMATH Keywords

linear programminggraphsworst-case analysis3-regularcubic

Mathematics Subject Classification ID

Integer programming (90C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Approximation hardness of edge dominating set problems ⋮ Minimum independent dominating sets of random cubic graphs ⋮ Minimum maximal matchings in cubic graphs ⋮ Independent dominating sets in regular graphs ⋮ On the independent domination number of regular graphs ⋮ A tight bound for independent domination of cubic graphs without 4‐cycles ⋮ A structural approach for independent domination of regular graphs ⋮ Connected domination of regular graphs

This page was built for publication: Linear programming and the worst-case analysis of greedy algorithms on cubic graphs