| Article ID: | iaor20042831 |
| Country: | United Kingdom |
| Volume: | 30 |
| Issue: | 13 |
| Start Page Number: | 1931 |
| End Page Number: | 1944 |
| Publication Date: | Nov 2003 |
| Journal: | Computers and Operations Research |
| Authors: | Fujie Tetsuya |
| Keywords: | graphs |
Given a connected graph, the Maximum Leaf Spanning Tree Problem (MLSTP) is to find a spanning tree whose number of leaves (degree-one vertices) is maximum. We propose a branch-and-bound algorithm for MLSTP, in which an upper bound is obtained by solving a minimum spanning tree problem. We report computational results for randomly generated and grid graphs with up to 100 vertices.