Title: Problemas de emparejamiento, cubrimiento y coloración en grafos_teoría y aplicaciones
University that offers the project: University of Santiago de Compostela
Director: Casas Méndez, Balbina Virginia
Student: Asorey Abelleira, Rodrigo
Summary:
Los problemas de cubrimiento de vértices, emparejamiento de aristas o coloración de vértices y de aristas constituyen algunos de los temas fundamentales que abarca la teoría de grafos, en general, y donde la clase de
grafos bipartitos desempeña un papel singular. Son de especial interés los algoritmos que permiten resolver estos problemas así como sus aplicaciones, entre las que se encuentran los problemas de asignación, de diseño de
horarios o de almacenamiento. Este trabajo pretende abarcar la presentación formal de estos problemas de la teoría de grafos, algunos de los resultados más relevantes en este contexto, algoritmos que han sido diseñados para su
resolución junto con aspectos computacionales destacados y, finalmente, aplicaciones en problemas de la vida real.
Referencias:
Bondy, J. A. and Murty, U. S. R. (1976) Graph Theory with Applications. North-Holland.
Bondy, J. A. and Murty, U. S. R. (2008) Graph Theory. Springer.
Diestel, R. (2017) Graph Theory. Springer.
Harris, J. M., Hirst, J. L. and Mossinghoff, M. J. (2008) Combinatorics and Graph Theory. Springer.
Pardalos, P. M., Du, D.-Z. and Graham, R. L. (2005) Handbook of Combinatorial Optimization. Springer.
Yadav, S. K. (2023) Advanced Graph Theory. Springer.
| More information |