Networks · 2004 · 36 citations · 9 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationCombinatorial OptimizationDiscrete OptimizationGraph AlgorithmsGraph TheoryInteger Programming
Abstract 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.
9
Approximation Algorithms for Connected Dominating Sets
Suvajyoti Guha, Samir Khuller · Algorithmica · 1998 · 1.1K citations
Approximating Maximum Leaf Spanning Trees in Almost Linear Time
Hsueh-I Lu, R. Ravi · Journal of Algorithms · 1998 · 119 citations