Minimum spanning tree cycle intersection problem

DOI10.1016/J.DAM.2021.01.031MaRDI QIDQ2656964zbMATH OpenOpenAlexFDO

Authors Manuel Dubinsky, César Massri, Gabriel Taubin

Publication date 17 March 2021

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

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

zbMATH Keywords

cycle basesspanning trees

Mathematics Subject Classification ID

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

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.

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

Cites work

• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Algorithms for Generating Fundamental Cycles in a Graph
• Atom-bond connectivity index of trees
• Classes of cycle bases
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• scientific article; zbMATH DE number 3508539 (Why is no real title available?)
• scientific article; zbMATH DE number 3243268 (Why is no real title available?)
• scientific article; zbMATH DE number 3338382 (Why is no real title available?)
• scientific article; zbMATH DE number 3024665 (Why is no real title available?)
• Lectures on matroids
• Minimum cycle bases for network graphs
• Practical graph isomorphism. II.

Cited in

(3)

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

Describes a project that uses

Uses Software

• Traces
• nauty

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)