| Revista: | Programación matemática y software |
| Base de datos: | |
| Número de sistema: | 000573133 |
| ISSN: | 2007-3283 |
| Autores: | Sierra-Alva, Luis Ernesto1 Marcial Romero, José Raymundo2 De Ita, Guillermo3 Hernández Servín, José Antonio4 |
| Instituciones: | 1Facultad de Ingeniería, UAEM, Cerro de Coatepec s/n, Ciudad Universitaria, 50100, Toluca, Estado de México, México., 2Facultad de Ingenería, UAEM, Cerro de Coatepec s/n, Ciudad Universitaria, 50100, Toluca, Estado de México, México., 3Facultad de Ciencias de la Computación, BUAP, Avenida San Claudio y 14 Sur, Ciudad Universitaria, 72592, Puebla, México., 4Facultad de Ingeniería, UAEM, Cerro de Coatepec s/n, Ciudad Universitaria, 50100, Toluca, Estado de México, México, |
| Año: | 2017 |
| Volumen: | 9 |
| Número: | 1 |
| Paginación: | 11-19 |
| País: | México |
| Idioma: | Español |
| Resumen en inglés | In this article we present an algorithm for counting edge covers of graphs. The algorithm,implemented in the C language, divides the input graph into sub-graphs until no intersected cycles are presented (shared cycles). Each sub-graph constitutes a node of a tree where the leaves are su subgraphs without intersected cycles. Hence, the edge covers counting is carry on on the leaves of the tree. |
| Resumen en español | 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. |
| Palabras clave: | Coberturas de Aristas, Teoría de Grafos, Problemas #P |
| Keyword: | Edge Covers, GraphTheory, #P Problems |
| Texto completo: | Texto completo (Ver PDF) |
