Repositorio de grafos para el conteo de conjuntos independientes
Resumen
La teoría de grafos es empleada en infinidad de aplicaciones en las áreas de química, comunicaciones, control, modelos de transporte, robótica por lo que resulta indispensable contar con herramientas que permitan el diseño y análisis de problemas que involucren su modelado mediante estas estructuras. Por esta razón se propone un sistema con dos usos, por un lado un editor gráfico que permita diseñar grafos con topologías precisas para grafos ponderados para exportarlos y tenerlos disponibles en el uso de otras aplicaciones y por otro lado una interfaz que con entradas específicas calcule propiedades típicas de los grafos como los conjuntos independientes.
Palabra(s) Clave(s): conjuntos independientes, editor gráfico, grafos, repositorio.
Texto completo:
1731-1750 PDFReferencias
S. Miranda, Modelo para la generación automática de resúmenes abstractos basado en grafos conceptuales. 2013. Instituto Politécnico Nacional. México.121 p.
Rafael López Bracho, María Paula Ortuño Sánchez, Un algoritmo paralelo para el problema del conjunto independiente, Revista de Matemática: Teoría y Aplicaciones. Vol. 7. No. 1-2. 2000.: 125-134 pp.
K. XU. Benchmarks with Hidden Optimum Solutions for Graph Problems Disponible en: http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graphbenchmarks. htm. Consulta 23 de enero de 2015.
Graph Theory, MathWorld. Disponible en: http://mathworld.wolfram.com/topics/GraphTheory.html. Consulta: 16 de enero de 2015.
R. Guerequeta, A. Vallecillo, Técnicas de Diseño de Algoritmos. 2da edición. 1998. Servicio de Publicaciones de la Universidad de Málaga. España.
R. Espinioza, Á. Lluch, Introducción a la teoría de grafos. 1997. Ediciones de la Universdad de Simón Bolívar. Colombia.
R. Diestel, Graph Theory. 4ª edición. 2010. Springer. Estados Unidos.
I. Kuckir, Graph drawer, Imágenes de grafos tomadas de http://g.ivank.net/. Consulta: 2011.
R. L. Shackelford, Computing and algorithms. 1998. Addison-Wesley.
S. Baase, V. Gelder, Algoritmos computacionales. 3ra edición. 2002. Addison-Wesley.
C. Greenhill, “The Complexity of Counting Colourings and Independent Sets in Sparse Graphs and Hypergraphs”. Computational Complexity. Vol. 9. No. 1. 2000.
S. P. Vadhan, The Complexity of Counting. Undergraduate thesis. Hardvard University. 1995.
M. Xiao, H. Nagamochi, An exact algorithm for maximum independent set in degree-5 graphs. Discrete Applied Mathematics. 2014.
N. Nash, S. Lelait, D. Gregg, Efficiently Implementing Maximum Independent Set Algorithms on Circle Graphs. ACM Journal of Experimental Algorithmics. Vol. 13. December 2008.
URL de la licencia: https://creativecommons.org/licenses/by/3.0/deed.es
Pistas Educativas está bajo la Licencia Creative Commons Atribución 3.0 No portada. 
TECNOLÓGICO NACIONAL DE MÉXICO / INSTITUTO TECNOLÓGICO DE CELAYA
Antonio García Cubas Pte #600 esq. Av. Tecnológico, Celaya, Gto. México
Tel. 461 61 17575 Ext 5450 y 5146
pistaseducativas@itcelaya.edu.mx