Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436153 | Theoretical Computer Science | 2015 | 17 Pages |
Abstract
We prove the first logarithmic lower bounds for the approximability of the Minimum Dominating Set problem for the case of connected (α,β)(α,β)-power law graphs for α being a size parameter and β the power law exponent. We give also a best up to now upper approximation bound for this problem in the case of the parameters β>2β>2. We develop also a new functional method for proving lower approximation bounds and display a sharp approximation phase transition area between approximability and inapproximability of the underlying problems. Our results depend on a method which could be also of independent interest.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mikael Gast, Mathias Hauptmann, Marek Karpinski,