Distributed Approximation Algorithms for Planar Graphs

1. Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network Decomposition and Locality in Distributed Computation. In: Proc. 30th IEEE Symp. on Foundations of Computer Science, pp. 364–369 (1989)

   Google Scholar 

2. Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control 70, 32–53 (1986)

   Article  MATH  MathSciNet  Google Scholar 

3. Czygrinow, A., Hańćkowiak, M.: Distributed Algorithm for Better Approximation of the Maximum Matching. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol. 2697, pp. 242–251. Springer, Heidelberg (2003)

   Chapter  Google Scholar 

4. Czygrinow, A., Hańćkowiak, M.: Distributed algorithms for weighted problems in sparse graphs. To appear in Journal of Discrete Algorithms (in Press) (Available online September 7, 2005)

   Google Scholar 

5. Czygrinow, A., Hańćkowiak, M., Szymańska, E.: Distributed algorithm for approximating the maximum matching. Discrete Applied Mathematics 143(1-3), 62–71 (2004)

   Article  MATH  MathSciNet  Google Scholar 

6. Czygrinow, A., Hańćkowiak, M., Szymańska, E.: A fast distributed algorithm for approximating the maximum matching. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 252–263. Springer, Heidelberg (2004)

   Chapter  Google Scholar 

7. Dubhashi, D., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons. In: Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 717–724 (2003)

   Google Scholar 

8. Elkin, M.: An Overview of Distributed Approximation. ACM SIGACT News Distributed Computing Column 35(4) (Whole number 132), 40–57 (2004)

   Google Scholar 

9. Hakimi, S., Mitchem, J., Schmeichel, E.: Star arboricity of graphs. Discrete Mathematics 149(1-3), 93–98 (1996)

   Article  MATH  MathSciNet  Google Scholar 

10. Hańćkowiak, M., Karoński, M., Panconesi, A.: A faster distributed algorithm for computing maximal matching deterministically. In: Proceedings of PODC 1999, the Eighteen Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 219–228 (1999)

    Google Scholar 

11. Jia, L., Rajaraman, R., Suel, R.: An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In: Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC), pp. 33–42 (2001)

    Google Scholar 

12. Kutten, S., Peleg, D.: Fast distributed construction of k-dominating sets and applications. In: Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, pp. 238–251 (1995)

    Google Scholar 

13. Kuhn, F., Wattenhofer, R.: Constant-Time Distributed Dominating Set Approximation. In: 22nd ACM Symposium on the Principles of Distributed Computing (PODC), Boston, Massachusetts, USA (July 2003)

    Google Scholar 

14. Kuhn, F., Moscibroda, T., Wattenhofer, R.: What Cannot Be Computed Locally! In: Proceedings of 23rd ACM Symposium on the Principles of Distributed Computing (PODC), pp. 300–309 (2004)

    Google Scholar 

15. Linial, N.: Locality in distributed graph algorithms. SIAM Journal on Computing 21(1), 193–201 (1992)

    Article  MATH  MathSciNet  Google Scholar 

16. Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036–1053 (1986)

    Article  MATH  MathSciNet  Google Scholar 

17. Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)

    Book  MATH  Google Scholar 

Download references