Repositorio de grafos para el conteo de conjuntos independientes

Juan Antares Perdomo Flandez, Pedro Bello López, Meliza Contreras González, Brayan Chavez Benavides

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 PDF

Referencias


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.


Enlaces refback

  • No hay ningún enlace refback.




URL de la licencia: https://creativecommons.org/licenses/by/3.0/deed.es

Licencia Creative Commons    Esta revista está bajo una Licencia Creative Commons Atribución 3.0 No portada.