Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
On Constant Time Approximation of Parameters of Bounded Degree Graphs
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
How well can the maximum size of an independent set, or the minimum size of a dominating set of a graph in which all degrees are at most
d
be approximated by a randomized constant time algorithm ? Motivated by results and questions of Nguyen and Onak, and of Parnas, Ron and Trevisan, we show that the best approximation ratio that can be achieved for the first question (independence number) is between Ω(
d
/log
d
) and
O
(
d
loglog
d
/ log
d
), whereas the answer to the second (domination number) is (1 +
o
(1)) ln
d
.