Distributed Large Independent Sets in One Round On Boundedindependence Graphs
 Publisher: SpringerVerlag Berlin Heidelberg

Related identifiers: doi: 10.1007/9783662486535_37 
Subject: [ INFO.INFODC ] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]

References
(21)
1. Alon, N., Spencer, J.H.: The probabilistic method. John Wiley & Sons (2004)
2. Barenboim, L.: On the locality of some NPcomplete problems. In: Proc.of International Colloquium on Automata, Languages, and Programming, ICALP'12 (2). pp. 403{415 (2012)
3. Caro, Y.: New results on the independence number. Tech. rep., Tel Aviv University (1979)
4. Cornejo, A., Kuhn, F.: Deploying wireless networks with beeps. In: Proceedings of the 24th International Conference on Distributed Computing. pp. 148{162. DISC'10, SpringerVerlag, Berlin, Heidelberg (2010), http://dl.acm.org/citation.cfm?id=1888781.1888802
5. Czygrinow, A., Hanckowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Proceedings of the 22Nd International Symposium on Distributed Computing. pp. 78{92. DISC '08, SpringerVerlag, Berlin, Heidelberg (2008)
6. Halldorsson, B.V., Halldorsson, M.M., Losievskaja, E., Szegedy, M.: Streaming algorithms for independent sets. In: Abramsky, S., Gavoille, C., Kirchner, C., auf der Heide, F.M., Spirakis, P.G. (eds.) ICALP (1). Lecture Notes in Computer Science, vol. 6198, pp. 641{652. Springer (2010)
7. Halldorsson, M.M.: Wireless scheduling with power control. ACM Trans. Algorithms 9(1), 7:1{7:20 (Dec 2012)
8. Halldorsson, M.M., Konrad, C.: Distributed algorithms for coloring interval graphs. In: Proceedings of the 28th International Conference on Distributed Computing. DISC'14 (2014)
9. Halldorsson, M.M., Mitra, P.: Nearly optimal bounds for distributed wireless scheduling in the SINR model. In: Proceedings of the 38th International Conference on Automata, Languages and Programming  Volume Part II. pp. 625{636. ICALP'11, SpringerVerlag, Berlin, Heidelberg (2011), http://dl.acm.org/citation.cfm?id=2027223.2027287
10. Karp, R.M.: Reducibility Among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85{103. Plenum Press (1972)

Similar Research Results
(2)
SilenceBased Communication (2010) 74%ENTANGLED GAMES ARE HARD TO APPROXIMATE (2011) 72% 
Metrics
No metrics available

 Download from

INRIA a CCSD electronic archive server via INRIA a CCSD electronic archive server (Conference object, 2015)

Cite this publication