New branch-and-bound algorithms for k-cardinality tree problems |
| |
| Institution: | 1. Department for Hand, Plastic and Aesthetic Surgery, Ludwig – Maximilian University Munich, Germany;2. Department of Clinical Anatomy, Mayo Clinic College of Medicine and Science, Rochester, MN, USA;3. Duke University Medical Center, Durham, NC, USA;4. Private Practice, Amsterdam, Netherlands;1. Department of Management, University of Toronto Scarborough and Rotman School of Management, University of Toronto, 1265 Military Trail, Toronto, Ontario M1C 1A4, Canada;2. Faculty of Engineering and Sciences, Universidad Adolfo Ibáñez, Av. Padre Hurtado 750, Viña del Mar, Chile;1. Research Center for Underground Space, Army Engineering University of PLA, Nanjing 210007, PR China;2. Shanghai Municipal Engineering Design Institute (Group) Co., Shanghai 200092, PR China |
| |
| Abstract: | Given an undirected graph, the k-cardinality tree problem (KCTP) is the problem of finding a subtree with exactly k edges whose sum of weights is minimum. In this paper we present a lower bound for KCTP based on the work by Kataoka et al. Kataoka, S., N. Araki and T. Yamada, Upper and lower bounding procedures for the minimum rooted k-subtree problem, European Journal of Operational Research, 122 (2000), 561–569]. This new bound is the basis for the development of a branch-and-bound algorithm for the problem. Experiments carried out on instances from KCTLib revealed that the new exact algorithm largely outperforms the previous approach. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
