We consider the problem of partitioning the nodes of a graph with costs on its edges into subsets of given sizes so as to minimize the sum of the costs on all edges cut. This problem arises in several physical situations — for example, in assigning the components of electronic circuits to circuit boards to minimize the number of connections between boards. This paper presents a heuristic method for partitioning arbitrary graphs which is both effective in finding optimal partitions, and fast enough to be practical in solving large problems.
Notas/Comentarios de Félix Pérez:
Uno de los primeros trabajos que propone la utilización de la teoría de grafos a la colocación óptima de componentes de un circuito electrónico con objeto de minimizar el número de conexiones. No se consigue una solución cerrada pero los autores proponen algunas alternativas de carácter heurístico.
Uno de los primeros trabajos que propone la utilización de la teoría de grafos a la colocación óptima de componentes de un circuito electrónico con objeto de minimizar el número de conexiones. No se consigue una solución cerrada pero los autores proponen algunas alternativas de carácter heurístico.
Especificaciones
- Autor/es: B.W. Kernighan; S. Lin.
- Fecha: 1970-02
- Publicado en: The Bell System Technical Journal (Volume: 49, Issue: 2, February 1970, Pages: 291-307).
- Idioma: Inglés
- Formato: PDF
- Contribución: Félix Pérez Martínez.
- Palabras clave: Circuitos y sistemas, Matemáticas, Sistemas de control
