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

Autores/as

  • Jose Antonio Hernandez-Servin Facultad de Ingenieria, UAEM
  • J. Raymundo Marcial-Romero Facultad de Ingenieria, UAEM
  • Guillermo de Ita Facultad de Ciencias de la Computacion, BUAP

DOI:

https://doi.org/10.13053/cys-21-3-2244

Palabras clave:

Edge covering, graph theory, integer partition.

Resumen

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.

Descargas

Publicado

2016-12-26

Número

Vol. 21 Núm. 3 (2017): Thematic issue: Advances in Logic-based Methods for Intelligent Systems (J. C. Nieves, E. Hermann Haeusler, B. Lopes)

Sección

Articles of the Thematic Issue

Licencia

Transfiero exclusivamente a la revista “Computación y Sistemas”, editada por el Centro de Investigación en Computación (CIC), los Derechos de Autor del artículo antes mencionado, asimismo acepto que no serán transferidos a ninguna otra publicación, en cualquier formato, idioma, medio existente (incluyendo los electrónicos y multimedios) o por desarrollar.

Certifico que el artículo, no ha sido divulgado previamente o sometido simultáneamente a otra publicación y que no contiene materiales cuya publicación violaría los Derechos de Autor u otros derechos de propiedad de cualquier persona, empresa o institución. Certifico además que tengo autorización de la institución o empresa donde trabajo o estudio para publicar este Trabajo.

El autor, representante acepta la responsabilidad por la publicación del Trabajo en nombre de todos y cada uno de los autores.

Esta Transferencia está sujeta a las siguientes reservas:

  • Los autores conservan todos los derechos de propiedad (tales como derechos de patente) de este Trabajo, con excepción de los derechos de publicación transferidos al CIC, mediante este documento.
  • Los autores conservan el derecho de publicar el Trabajo total o parcialmente en cualquier libro del que ellos sean autores o editores y hacer uso personal de este trabajo en conferencias, cursos, páginas web personal, etc.