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

Abstract

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.

Keywords

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