G. Taubin

collaborators

4 papers

cs.DM2024

Lower Bounds for the Minimum Spanning Tree Cycle Intersection Problem

Manuel Dubinsky, Kun-Mao Chao, CÃ©sar Massri +1

Minimum spanning trees are important tools in the analysis and design of networks. Many practical applications require their computation, ranging from biology and linguistics to ec…

cs.DM2024

tinygarden -- A java package for testing properties of spanning trees

Manuel Dubinsky, CÃ©sar Massri, Gabriel Taubin

Spanning trees are fundamental objects in graph theory. The spanning tree set size of an arbitrary graph can be very large. This limitation discourages its analysis. However intere…

math.CO2024

Three aspects of the MSTCI problem

Consider a connected graph $G$ and let $T$ be a spanning tree of $G$ . Every edge $e \in G - T$ induces a cycle in $T \cup {e}$ . The intersection of two distinct such cycles is the…

cs.DM2024

Minimum Spanning Tree Cycle Intersection Problem

Consider a connected graph $G$ and let $T$ be a spanning tree of $G$ . Every edge $e \in G - T$ induces a cycle in $T \cup {e}$ . The intersection of two distinct such cycles is the…