Low-Exponential Algorithm for Counting the Number of Edge Cover on Simple Graphs



Título del documento: Low-Exponential Algorithm for Counting the Number of Edge Cover on Simple Graphs
Revista: Computación y sistemas
Base de datos: PERIÓDICA
Número de sistema: 000423346
ISSN: 1405-5546
Autores: 1
1
2
Instituciones: 1Universidad Autónoma del Estado de México, Toluca, Estado de México. México
2Benemérita Universidad Autónoma de Puebla, Puebla. México
Año:
Periodo: Jul-Sep
Volumen: 21
Número: 3
País: México
Idioma: Inglés
Tipo de documento: Artículo
Enfoque: Aplicado, descriptivo
Resumen en inglés A procedure for counting edge covers of simple graphs is presented. The procedure splits simple graphs into non-intersecting cycle graphs. This is a “low exponential” exact algorithm to count edge covers for simple graphs whose upper bound in the worst case is O(1.465575(m−n) × (m + n)), where m and n are the number of edges and nodes of the input graph, respectively
Disciplinas: Ciencias de la computación
Palabras clave: Procesamiento de datos,
Procesamiento de imágenes,
Cubrimiento de bordes,
Teoría de grafos,
Partición
Keyword: Data processing,
Image processing,
Edge covering,
Graph theory,
Partition
Texto completo: Texto completo (Ver HTML) Texto completo (Ver PDF)