Upper and lower bounding procedures for minimum rooted k-subtree problem

Upper and lower bounding procedures for minimum rooted k-subtree problem

0.00 Avg rating0 Votes
Article ID: iaor2001907
Country: Netherlands
Volume: 122
Issue: 3
Start Page Number: 561
End Page Number: 569
Publication Date: May 2000
Journal: European Journal of Operational Research
Authors: , ,
Keywords: graphs
Abstract:

Given an undirected graph and a fixed root node on it, the minimum rooted k-subtree problem is the problem of finding a minimum-cost connected subtree with exactly k edges that includes the root node. Applications of this problem appear in several fields. The problem is proved to be NP-hard. Due to the existence of a root node, we are able to derive a greedy procedure that gives a stronger lower-bound to this problem than those in earlier studies. Heuristics are also discussed to obtain an upper bound. Computational results indicate that the proposed lower bounding procedure is effective when k is small. Especially for grid-type graphs, we observe that the upper and lower bounds frequently coincide with each other.

Reviews

Required fields are marked *. Your email address will not be published.