A polynomial bound on the number of light cycles in an undirected graph
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 |