One-way Communication Complexity of Minimum Vertex Cover in General Graphs

Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman

We study the communication complexity of the Minimum Vertex Cover (MVC) problem on general graphs within the \(k\)-party one-way communication model. Edges of an arbitrary \(n\)-ve…