The family of cost monotonic and cost additive rules in minimum cost spanning tree problems
- Bergantiños Cid, Gustavo
- Lorenzo Picado, Leticia
- Lorenzo Freire, Silvia
Publisher: Comité organizador del XXX Congreso Nacional de Estadística e Investigación Operativa y IV Jornadas de Estadística Pública
ISBN: 978-84-690-7249-3
Year of publication: 2007
Congress: Congreso Nacional de Estadística e Investigación Operativa (30. 2007. Valladolid)
Type: Conference paper
Abstract
In this paper we define a new family of rules in minimum cost spanning tree problems related with Kruskal�s algorithm. We characterize this family with a cost monotonicity property and a cost additivity property. Adding the property of core selection (or separability) to the previous characterization, we obtain the family of obligation rules defined in Tijs et al (2006). Keywords: minimum cost spanning tree problems, cost monotonicity, cost additivity.