Low-Exponential Algorithm for Counting the Number of Edge Cover on Simple Graphs
Abstract: 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.
Saved in:
Main Authors: | , , |
---|---|
Format: | Digital revista |
Language: | English |
Published: |
Instituto Politécnico Nacional, Centro de Investigación en Computación
2017
|
Online Access: | http://www.scielo.org.mx/scielo.php?script=sci_arttext&pid=S1405-55462017000300449 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|