What Cannot Be Computed Locally!
- Fabian Kuhn ,
- Thomas Moscibroda ,
- Roger Wattenhofer
PODC 2004: 23rd ACM Symposium on the Principles of Distributed Computing, St. John's, Newfoundland, Canada |
Best Student Paper Award
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). See attachment for full abstract.