A polynomial bound on the number of light cycles in an undirected graph


Autoria(s): Subramanian, Ashok
Data(s)

24/02/1995

Resumo

Let G be an undirected graph with a positive real weight on each edge. It is shown that the number of minimum-weight cycles of G is bounded above by a polynomial in the number of edges of G. A similar bound holds if we wish to count the number of cycles with weight at most a constant multiple of the minimum weight of a cycle of G.

Formato

application/pdf

Identificador

http://eprints.iisc.ernet.in/38133/1/A_polynomial_bound_on.pdf

Subramanian, Ashok (1995) A polynomial bound on the number of light cycles in an undirected graph. In: Information Processing Letters, 53 (4). pp. 173-176.

Publicador

Elsevier Science

Relação

http://dx.doi.org/10.1016/0020-0190(94)00202-A

http://eprints.iisc.ernet.in/38133/

Palavras-Chave #Computer Science & Automation (Formerly, School of Automation)
Tipo

Journal Article

PeerReviewed