What Cannot Be Computed Locally!
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.