Computing a tree having a small vertex cover

Takuro Fukunaga, Takanori Maehara

We consider a new Steiner tree problem, called vertex-cover-weighted Steiner tree problem. This problem defines the weight of a Steiner tree as the minimum weight of vertex covers…