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
Editorial: 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
Ano de publicación: 2007
Congreso: Congreso Nacional de Estadística e Investigación Operativa (30. 2007. Valladolid)
Tipo: Achega congreso
Resumo
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.