This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Avenali, A. Search for Related Content

Resolution Branch and Bound and an Application: The Maximum Weighted Stable Set Problem

Dipartimento di Informatica e Sistemistica, Università degli Studi di Roma "La Sapienza," 00185 Roma, Italy
avenali{at}dis.uniroma1.it

We propose a new resolution algorithm, called resolution branch and bound (RBB), where a branch-and-bound scheme is empowered by exploiting the information contained in a family of closed subproblems, collected by a full resolution phase. In particular, we use this information to define a new branching rule that seems able to reduce the risk of incurring inappropriate branchings. We apply RBB and the proposed branching rule to the maximum weighted stable set problem, as its features allow us to speed up a time-consuming step in the full resolution phase. To compute upper bounds, we generalize to the weighted case the polynomial time procedure provided by Mannino and Sassano [Mannino, C., A. Sassano. 1994. An exact algorithm for the maximum stable set problem. Computational Optim. Appl. 3 243–258] for the unweighted case. Computational results validate the effectiveness of the provided branching rule and the good performance of RBB on many DIMACS benchmarks.

Subject classifications: mathematics; combinatorics; programming; integer; algorithms; branch and bound; networks/graphs.
History: Received November 2002; revision received February 2006; accepted March 2006.