Local algorithms in (weakly) coloured graphs

On a problem of formal logic

Frank P. Ramsey · 1930

Earlier work this paper cites.

Dana Angluin. Local and global properties in networks of processors. In Proc. 12th Annual ACM Symposium on Theory of Computing (STOC, Los Angeles, CA, USA, April 1980)

1980

Earlier work this paper cites.

Egon Balas, Donald Miller, Joseph Pekny, and Paolo Toth. A parallel shortest augmenting path algorithm for the assignment problem. Journal of the ACM

1991

Earlier work this paper cites.

Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing

1992

Earlier work this paper cites.

Alain Mayer, Moni Naor, and Larry Stockmeyer. Local computations on static and dynamic graphs. In Proc. 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS, Tel Aviv, Israel, January 1995)

1995

Earlier work this paper cites.

Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM Journal on Computing

1995

Earlier work this paper cites.

On the distributed complexity of computing maximal matchings

Michał Hańćkowiak, Michał Karoński, and Alessandro Panconesi · 1998

Earlier work this paper cites.

Shay Kutten and David Peleg. Fast distributed construction of small k k -dominating sets and applications. Journal of Algorithms

1998

Cited alongside, same era.

Mirjam Wattenhofer and Roger Wattenhofer. Distributed weighted matching. In Proc. 18th International Symposium on Distributed Computing (DISC, Amsterdam, Netherlands, October 2004)

Original

2004

Cited alongside, same era.

The Price of Locality: Exploring the Complexity of Distributed Coordination Primitives

Fabian Kuhn · 2005

Cited alongside, same era.

Fabian Kuhn and Roger Wattenhofer. Constant-time distributed dominating set approximation. Distributed Computing

2005

Cited alongside, same era.

Jaap-Henk Hoepman, Shay Kutten, and Zvi Lotker. Efficient distributed weighted matchings on trees. In Proc. 13th International Colloquium on Structural Information and Communication Complexity (SIROCCO, Chester, UK, July 2006)

Andrzej Czygrinow, Michał Hańćkowiak, and Wojciech Wawrzyniak. Fast distributed approximations in planar graphs. In Proc. 22nd International Symposium on Distributed Computing (DISC, Arcachon, France, September 2008)

2008

Later among the works it cites.

Christoph Lenzen, Yvonne Anne Oswald, and Roger Wattenhofer. What can be approximated locally? In Proc. 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA, Munich, Germany, June 2008)

2008

Later among the works it cites.

Christoph Lenzen and Roger Wattenhofer. Leveraging Linial’s locality limit. In Proc. 22nd International Symposium on Distributed Computing (DISC, Arcachon, France, September 2008)

2008

Later among the works it cites.

Huy N. Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local improvements. In Proc. 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS, Philadelphia, PA, USA, October 2008)

2008

Later among the works it cites.