Brief Announcement: Local Independent Set Approximation

被引：11

作者：

Bodlaender, Marijke H. L. ^{[1
]}

Halldorsson, Magnus M. ^{[1
]}

Konrad, Christian ^{[1
]}

Kuhn, Fabian ^{[2
]}

机构：

[1] Reykjavik Univ, Sch Comp Sci, ICE TCS, Reykjavik, Iceland

[2] Univ Freiburg, Dept Comp Sci, Freiburg, Germany

来源：

PROCEEDINGS OF THE 2016 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'16) | 2016年

关键词：

Local algorithms; maximum independent set; network decompositions;

D O I：

10.1145/2933057.2933068

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：93 / 95

页数：3

共 11 条

[1] NETWORK DECOMPOSITION AND LOCALITY IN DISTRIBUTED COMPUTATION [J].

AWERBUCH, B ;

LUBY, M ;

GOLDBERG, AV ;

PLOTKIN, SA .

30TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 1989, :364-369

[2]

Barenboim Leonid, 2015, Structural Information and Communication Complexity. 22nd International Colloquium, SIROCCO 2015. Post-Proceedings: LNCS 9439, P209, DOI 10.1007/978-3-319-25258-2_15

[3]

Barenboim L, 2012, LECT NOTES COMPUT SC, V7392, P403, DOI 10.1007/978-3-642-31585-5_37

[4] Distributed Large Independent Sets in One Round on Bounded-Independence Graphs [J].

Halldorsson, Magnus M. ;

Konrad, Christian .

DISTRIBUTED COMPUTING (DISC 2015), 2015, 9363 :559-572

[5] Clique is hard to approximate within n1-ε [J].

Håstad, J .

ACTA MATHEMATICA, 1999, 182 (01) :105-142

[6]

Kuhn Fabian, 2004, 23 ACM S PRINC DISTR

[7] LOW DIAMETER GRAPH DECOMPOSITIONS [J].

LINIAL, N ;

SAKS, M .

COMBINATORICA, 1993, 13 (04) :441-454

[8] LOCALITY IN DISTRIBUTED GRAPH ALGORITHMS [J].

LINIAL, N .

SIAM JOURNAL ON COMPUTING, 1992, 21 (01) :193-201

[9] RAMANUJAN GRAPHS [J].

LUBOTZKY, A ;

PHILLIPS, R ;

SARNAK, P .

COMBINATORICA, 1988, 8 (03) :261-277

[10] On the complexity of distributed network decomposition [J].

Panconesi, A ;

Srinivasan, A .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1996, 20 (02) :356-374

← 1 2 →