Minimum Spanning Tree Cycle Intersection Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929322081648640 |
|---|---|
| author | Dubinsky, Manuel Massri, César Taubin, Gabriel |
| author_facet | Dubinsky, Manuel Massri, César Taubin, Gabriel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2102_13193 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Minimum Spanning Tree Cycle Intersection Problem Dubinsky, Manuel Massri, César Taubin, Gabriel Discrete Mathematics Combinatorics 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. |
| title | Minimum Spanning Tree Cycle Intersection Problem |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2102.13193 |