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.