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.

Research Areas

  • Systems and networking