Minimum spanning tree cycle intersection problem

DOI10.1016/J.DAM.2021.01.031zbMATH Open1464.05038arXiv2102.13193OpenAlexW3129739404MaRDI QIDQ2656964FDOQ2656964

Authors: Manuel Dubinsky, César Massri, Gabriel Taubin 

Publication date: 17 March 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Consider a connected graph $G$ and let $T$ be a spanning tree of $G$. Every edge $einG-T$ induces a cycle in $Tcupe$. 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.

Full work available at URL: https://arxiv.org/abs/2102.13193

Recommendations

• Proof of a conjecture about minimum spanning tree cycle intersection
• On the minimum diameter spanning tree problem
• The minimum-area spanning tree problem
• Algorithms and Data Structures
• The Minimum Spanning Tree Constraint
• Minimum Diameter Spanning Trees and Related Problems
• The minimum spanning tree problem on a planar graph
• A practical minimum spanning tree algorithm using the cycle property
• Minimum spanning hypertrees
• Minimum spanning trees

zbMATH Keywords

spanning treescycle bases

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38)

Cites Work

• Practical graph isomorphism. II.
• Lectures on matroids
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Algorithms for Generating Fundamental Cycles in a Graph
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• Atom-bond connectivity index of trees
• Minimum cycle bases for network graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Classes of cycle bases
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• Minimum spanning tree cycle intersection problem on outerplanar graphs
• Proof of a conjecture about minimum spanning tree cycle intersection
• Cycle intersection in spanning trees: a shorter proof of a conjecture and applications

Uses Software

• nauty
• Traces

This page was built for publication: Minimum spanning tree cycle intersection problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2656964)