The (K,k) ‐capacitated spanning tree problem

The (K,k) ‐capacitated spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor20125789
Volume: 9
Issue: 4
Start Page Number: 258
End Page Number: 266
Publication Date: Nov 2012
Journal: Discrete Optimization
Authors: , ,
Keywords: capacitated arc routing problem, minimum spanning trees
Abstract:

This paper considers a generalization of the capacitated spanning tree problem, in which some of the vertices have capacity K equ1, and the others have capacity k < K equ2. We prove that the problem can be approximated within a constant factor, and present better approximations when k equ3 is 1 or 2.

Reviews

Required fields are marked *. Your email address will not be published.