Implementación de un método para generar coberturas de aristas en grafos simples.

Autores/as

  • Luis Ernesto Sierra-Alva Facultad de Ingeniería, UAEM, Cerro de Coatepec s/n, Ciudad Universitaria, 50100, Toluca, Estado de México, México.
  • José Raymundo Marcial Romero Facultad de Ingenería, UAEM, Cerro de Coatepec s/n, Ciudad Universitaria, 50100, Toluca, Estado de México, México.
  • Guillermo De Ita Facultad de Ciencias de la Computación, BUAP, Avenida San Claudio y 14 Sur, Ciudad Universitaria, 72592, Puebla, México.
  • José Antonio Hernández Servín Facultad de Ingeniería, UAEM, Cerro de Coatepec s/n, Ciudad Universitaria, 50100, Toluca, Estado de México, México

DOI:

https://doi.org/10.30973/progmat/2017.9.1/2

Palabras clave:

Coberturas de Aristas, Teoría de Grafos, Problemas #P

Resumen

En este artículo se presenta un algoritmo para contar las coberturas de aristas de un grafo. El algoritmo, implementado en el lenguaje de programación C++, consiste en dividir el grafo original en subgrafos que cumplan con la propiedad de no tener cíclicos intersectados (ciclos compartidos). Cada subgrafo consti-tuye un nodo de un árbol de subgrafos en donde las hojas del árbol son grafos sin ciclos intersectados. Por lo tanto, el conteo de coberturas se puede realizar sobre las hojas del árbol.

Biografía del autor/a

Luis Ernesto Sierra-Alva, Facultad de Ingeniería, UAEM, Cerro de Coatepec s/n, Ciudad Universitaria, 50100, Toluca, Estado de México, México.

Luis Ernesto Sierra-Alva, Egresado de la Facultad de Ingeniería de la Universidad Autónoma del Estado de México en la Carrera de Ingeniería en Computación. Participe como ponente en el congreso COMIA 2015 con el tema “Implementación de un método para generar coberturas de aristas en grafos simples”:

José Raymundo Marcial Romero, Facultad de Ingenería, UAEM, Cerro de Coatepec s/n, Ciudad Universitaria, 50100, Toluca, Estado de México, México.

José Raymundo Marcial Romero, Actualmente profesor investigador de tiempo completo en la Facultad de Ingeniería de la Universidad Autónoma del Estado de México. Miembro del Sistema Nacional de Investigadores del Consejo Nacional de Ciencia y Tecnología, Nivel 1. En el año 2000 obtuvo el título de Licenciatura en Ciencias de la Computación y en el año 2007 el grado de Doctor en Ciencias de la Computación por The University of Birmingham, UK, en The School of Computer Science.

Guillermo De Ita, Facultad de Ciencias de la Computación, BUAP, Avenida San Claudio y 14 Sur, Ciudad Universitaria, 72592, Puebla, México.

Guillermo De Ita, Obtuvo su doctorado en Ingeniería Eléctrica en el CINVESTAV del IPN, México. Trabajó por 10 años como desarrollador y consultor en sistemas de bases de datos y sistemas de información geográfica para diferentes empresas en México. Ha realizado estancias de investigación en la Universidad de Chicago, Texas A&M, INAOEP Puebla, UAEMEX-Toluca y en el instituto INRIA en Lille Francia. Ha asesorado más de 40 trabajos de tesis (ya concluidos) en el área de computación a nivel licenciatura y posgrado y ha publicado más 100 artículos de investigación con arbitraje riguroso. Actualmente es profesor investigador de la Facultad de Ciencias de la Computación, BUAP, Puebla, México y Miembro del SNI Nivel 1.

José Antonio Hernández Servín, Facultad de Ingeniería, UAEM, Cerro de Coatepec s/n, Ciudad Universitaria, 50100, Toluca, Estado de México, México

José Antonio Hernández Servín, Actualmente profesor investigador de tiempo completo en la Facultad de Ingeniería de la Universidad Autónoma del Estado de México. Miembro del Sistema Nacional de Investigadores del Consejo Nacional de Ciencia y Tecnología, Nivel 1. En 1999 obtuvo el título de Licenciado en Ciencias Fisico-Matématicas y terminó la Maestría en Matemáticas Puras en 2001 en la UMSNH (Univ. Aut. San Nicolás de Hidalgo). Para el año 2005, obtiene el Doctorado en Ciencias (PhD) por The University of Nottingham, UK, en The School of Electrical and Electronic Engineering, en el departamento de Óptica.

Citas

Jiang, Y., Xia, Z., & Zhong, Y. (2014). Autonomous trust construction in multi-agent systems—a graph theory methodology. Journal of Advances in Engineering Software 36 (2), 59 -66. https://doi.org/10.1016/j.advengsoft.2004.09.001

Núñez, J., Silvero, M., & Villar, M. (2012). Mathematical tools for the future: Graph Theory and graphicable algebras. Journal of Applied Mathematics and Computation 219 (11), 6113 - 6125. https://doi.org/10.1016/j.amc.2012.12.004

González-Díaz, H., Pérez-Montoto, L., & Paniagua, E. (2009). Generalize dlattice graphs for 2D-visualization of biological information. Journal of Theoretical Biology 261 (1), 136 - 147. https://doi.org/10.1016/j.jtbi.2009.07.029

Thomas, C., Lambrechts, J., Wolanskic, E., & Deleersnijdera, E. (2013). Numerical modelling and graph theory tools to study ecologicalconnectivity in the Great Barrier Reef. Journal of Ecological Modelling 272, 160 -174. https://doi.org/10.1016/j.ecolmodel.2013.10.002

Wanga, Y.-c., & Önal, H. (2011). Designing connected nature reserve networks using a graph theory approach. Journal of Acta Ecologica Sinica 31 (5), 235 -240. https://doi.org/10.1016/j.chnaes.2011.06.001

D. Phillips, J., Schwanghart, W., & Heckmann, T. (2015). Graph theory in the geosciences. Journal of Earth-Science Reviews 143, 147-160. https://doi.org/10.1016/j.earscirev.2015.02.002 https://doi.org/10.1016/j.earscirev.2015.02.002

Heckmann, T., Schwanghart, W., & D. Phillips, J. (2014). Graph theory—Recent developments of its application in geomorphology. Journal of Geomorphology. https://doi.org/10.1016/j.geomorph.2014.12.024

Abdul Rahman, A., Hamdan, M., & Ibrahim, M. (2014). The use of graphs in Malaysian companies’ corporate reports: A longitudinal study. Journal of Procedia - Social and Behavioral Sciences 164, 653 - 666. https://doi.org/10.1016/j.sbspro.2014.11.160

Schroeder Barwaldt, M., de Fátima Franzin, R., & Vanderlei dos Santos, A. (2014). Using the theory of graphs on the implementation of bike lane in small towns. Journal of Procedia - Social and Behavioral Sciences 162, 350 - 358. https://doi.org/10.1016/j.sbspro.2014.12.216

A. Best, L., D. Smith, L., & Stubbs, D. (2001). Graph use in psychology and other sciences. Journal of Behavioural Processes 54 (1-3), 155-165. https://doi.org/10.1016/S0376-6357(01)00156-5

Goldenberg, D., & Galván, A. (2015). The use of functional and effective connectivity techniques to understand the developing brain. Journal of Developmental Cognitive Neuroscience 12, 155 -164. https://doi.org/10.1016/j.dcn.2015.01.011

J. Phillips, D., McGlaughlin, A., & Soldan, A. (2015). Graph theoretic analysis of structural cconnectivity across the spectrum of Alzheimer3s disease: The importance of graph creation methods. Journal of NeuroImage: Clinical 7, 377-390. https://doi.org/10.1016/j.nicl.2015.01.007

Lin, C., Liu, J., & Lu, P. (2014). A Simple FPTAS for Counting Edge Covers. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, 341- 348. https://doi.org/10.1137/1.9781611973402.25

Hernández Servín, J., Marcial Romero , J., & De Ita, G. (2014). Low exponential algorithm for counting the number of edge cover on simple graphs. Proceedings of the Ninth Latin American Workshop on Logic/ Languages, Algorithms and New Methods of Reasoning. pp 1--8. 15. https://doi.org/10.13053/cys-21-3-2244

Bondy, J., & Murty, U. (2010). Graph Theory. Springer Verlag, Graduate Texts in Mathematics.

Descargas

Publicado

28-02-2017

Cómo citar

Sierra-Alva, L. E., Marcial Romero, J. R., De Ita, . G., & Hernández Servín, J. A. (2017). Implementación de un método para generar coberturas de aristas en grafos simples. Programación matemática Y Software, 9(1), 11–19. https://doi.org/10.30973/progmat/2017.9.1/2

Número

Vol. 9 Núm. 1 (2017): Febrero de 2017

Sección

Artículos

Licencia

Derechos de autor 2016 Luis Ernesto Sierra-Alva, José Raymundo Marcial Romero, Guillermo De Ita, José Antonio Hernández Servín

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Usted es libre de:

Compartir — compartir y redistribuir el material publicado en cualquier medio o formato.
Adaptar — combinar, transformar y construir sobre el material para cualquier propósito, incluso comercialmente.

Bajo las siguientes condiciones:

Atribución — Debe otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puede hacerlo de cualquier manera razonable, pero de ninguna manera que sugiera que el licenciador lo respalda a usted o a su uso.
  Sin restricciones adicionales: no puede aplicar términos legales o medidas tecnológicas que restrinjan legalmente a otros a hacer cualquier cosa que permita la licencia.