Suppose we are given a graph that is undirected and connected. In this graph, a vertex is specified as a root. A cost and a profit are also given to each corresponding edge and vertex, respectively. Then, maximum profitable subtree problem is a problem of finding a subtree that maximizes total profits within a prescribed amount of total cost. Of course, the resultant subtree must be connected and include the root. We propose some approximate and branch-and-bound algorithms to the problem and investigate the efficiency of these procedures with computational experiments.
展开▼
