Distributed Large Independent Sets in One Round On Bounded-independence Graphs

Conference object English OPEN
Halldorsson , Magnus M.; Konrad , Christian;
(2015)
  • Publisher: Springer-Verlag Berlin Heidelberg
  • Related identifiers: doi: 10.1007/978-3-662-48653-5_37
  • Subject: [ INFO.INFO-DC ] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]

International audience; We present a randomized one-round, single-bit messages, distributed algorithm for the maximum independent set problem in polynomially bounded-independence graphs with poly-logarithmic approximation factor. Bounded-independence graphs capture vari... View more
  • References (21)
    21 references, page 1 of 3

    1. Alon, N., Spencer, J.H.: The probabilistic method. John Wiley & Sons (2004)

    2. Barenboim, L.: On the locality of some NP-complete 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, Springer-Verlag, 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, Springer-Verlag, 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, Springer-Verlag, 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 (6)
  • Metrics
    No metrics available
Share - Bookmark