INVESTIGADORES
MASSRI Cesar Dario
artículos
Título:
Minimum Spanning Tree Cycle Intersection problem
Autor/es:
DUBINSKY, MANUEL; MASSRI, CÉSAR; TAUBIN, GABRIEL
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Año: 2021 vol. 294 p. 152 - 166
ISSN:
0166-218X
Resumen:
Consider a connected graph G and let T be a spanning tree of G. Every edge e∈G−T induces a cycle in T∪{e}. The intersection of two distinct such cycles is the set of edges of T that belong to both cycles. We consider the problem of finding a spanning tree that has the least number of such non-empty intersections. In this article we analyze the particular case of complete graphs, and formulate a conjecture for graphs that have a universal vertex.
