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 |