Distributed packing in planar graphs

ABSTRACT

We give an efficient distributed algorithm that finds an almost optimal packing of a graph H in a planar graph G. The algorithm is deterministic and its running time is poly-logarithmic in the order of G.

REFERENCES

• 1: B. Awerbuch , M. Luby , A. V. Goldberg , S. A. Plotkin, Network decomposition and locality in distributed computation, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.364-369, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63504]
• 2: Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
• 3: Andrzej Czygrinow , Michał Hańćkowiak, Distributed almost exact approximations for minor-closed families, Proceedings of the 14th conference on Annual European Symposium, p.244-255, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_24]
• 4: A. Czygrinow and M. Hanckowiak. Distributed approximation algorithms in unit-disk graphs. In S. Dolev, editor, DISC, volume 4167 of Lecture Notes in Computer Science, pages 385--398. Springer, 2006.
• 5: A. Czygrinow and M. Hanckowiak. Distributed approximation algorithms for weighted problems in minor-closed families. In G. Lin, editor, COCOON, volume 4598 of Lecture Notes in Computer Science, pages 515--525. Springer, 2007.
• 6: A. Czygrinow and M. Hanckowiak. Distributed approximations for packing in unit-disk graphs. In A. Pelc, editor, DISC, volume 4731 of Lecture Notes in Computer Science, pages 152--164. Springer, 2007.
• 7: A. Czygrinow, M. Hanckowiak, and E. Szymanska. Distributed approximation algorithms for planar graphs. In T. Calamoneri, I. Finocchi, and G. F. Italiano, editors, CIAC, volume 3998 of Lecture Notes in Computer Science, pages 296--307. Springer, 2006.
• 8: R. Diestel. Graph Theory, third (electronic) edition, volume 173 of New York Graduate Texts in Mathematics. Springer, 2005.
• 9: Michael Elkin, Distributed approximation: a survey, ACM SIGACT News, v.35 n.4, December 2004 [doi>10.1145/1054916.1054931]
• 10: Michał Hańćkowiak , Michał Karoński , Alessandro Panconesi, A faster distributed algorithm for computing maximal matchings deterministically, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.219-228, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301360]
• 11: F. Kuhn, T. Moscibroda, T. Nieberg, and R. Wattenhofer. Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In P. Fraigniaud, editor, Distributed algorithms, volume 3724 of Lecture Notes In Computer Science, pages 273--287, September 2005.
• 12: Fabian Kuhn , Tim Nieberg , Thomas Moscibroda , Roger Wattenhofer, Local approximation schemes for ad hoc and sensor networks, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080827]
• 13: Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992 [doi>10.1137/0221015]
• 14: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, distributed algorithms, graph packing