TY - GEN

T1 - On constant time approximation of parameters of bounded degree graphs

AU - Alon, Noga

N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.

PY - 2010

Y1 - 2010

N2 - 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/logd) and O(d loglogd/ logd), whereas the answer to the second (domination number) is (1 + o(1)) ln d.

AB - 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/logd) and O(d loglogd/ logd), whereas the answer to the second (domination number) is (1 + o(1)) ln d.

KW - constant time approximation

KW - dominating set in a graph

KW - independence number of a graph

UR - http://www.scopus.com/inward/record.url?scp=78449272771&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78449272771&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-16367-8_14

DO - 10.1007/978-3-642-16367-8_14

M3 - Conference contribution

AN - SCOPUS:78449272771

SN - 3642163661

SN - 9783642163661

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 234

EP - 239

BT - Property Testing - Current Research and Surveys

T2 - Mini-Workshop on Property Testing

Y2 - 8 January 2010 through 10 January 2010

ER -