Premium
The maximum‐leaf spanning tree problem: Formulations and facets
Author(s) -
Fujie Tetsuya
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20001
Subject(s) - spanning tree , combinatorics , polytope , minimum degree spanning tree , mathematics , minimum spanning tree , integer programming , k minimum spanning tree , connected dominating set , tree (set theory) , graph , linear programming relaxation , discrete mathematics , mathematical optimization , tree structure , binary tree , k ary tree
The Maximum Leaf Spanning Tree Problem (MLSTP) is to find a spanning tree in a given undirected graph, whose number of leaves (vertices of degree 1) is maximum. In this article, we consider an integer programming approach to the MLSTP. We provide two formulations of the MLSTP and study the facial structure of polytopes arising from the formulations. Moreover, several relaxation problems are compared. © 2004 Wiley Periodicals, Inc.