Un algoritmo exacto para el problema del árbol generador con el número máximo de hojas

  1. Sergio Alonso 1
  2. Miguel Ángel Domínguez Ríos
  3. Colebrook Santamaría, Marcos 1
  4. Antonio Sedeño Noda 1
  1. 1 Universidad de La Laguna
    info

    Universidad de La Laguna

    San Cristobal de La Laguna, España

    ROR https://ror.org/01r9z8p25

Proceedings:
XXVIII Congreso Nacional de Estadística e Investigación Operativa (SEIO 2004)

Publisher: Departamento de Estadística e Investigación Operativa, Universidad de Cádiz

ISBN: 84-689-0438-4

Year of publication: 2005

Pages: 421-422

Congress: XXVIII Congreso Nacional de Estadística e Investigación Operativa

Type: Conference paper

GOOGLE SCHOLAR

Abstract

Desarrollamos en este trabajo un m´etodo exacto tipo ramificaci´on y acotaci´on, para la construcci´on del ´arbol generador con el n´umero m´axi-mo de nodos-hoja, basado en estrategias enumerativas sobre el conjunto de ´arboles generadores de un grafo conexo.

Bibliographic References

  • [1] Fujie, T. (2003). An exact algorithm for the maximum leaf spanning tree problem. Computers & Operations Research, Vol 30, No 13, Pags 1931-1944.
  • [2] Garey M. R.;Johnson, D. S. (1979). Computers and Intractability: A guide to the theory of NP-completeness. W. H. Freeman, San Francisco.
  • [3] Prim RC. (1957). Shortest connection networks and some generalizations. Bell Systems Technical Journal, Vol 36, Pages 1389-401.