Expertini Research Research
Mathematics PDF Available DOI: 10.1016/j.dam.2021.01.031 Non-peer-reviewed Preprint

Minimum Spanning Tree Cycle Intersection Problem

Manuel Dubinsky, Cesar Massri, Gabriel Taubin  ·  Published 2021-02-25

Abstract

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 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.

Keywords

📄 Full Paper Available as PDF
This paper is available as a downloadable PDF.
📄 Download PDF

✨ AI Plain-English Summary

Get a plain-English summary of this paper generated by AI (5 free per day).

Comments (0)

No comments yet. Be the first to comment.