What Cannot Be Computed Locally!

Fabian Kuhn; Thomas Moscibroda; Roger Wattenhofer

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 | July 2004

Best Student Paper Award

Download BibTex

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.