Cover Image

Lower Bounds for the Minimum Spanning Tree Cycle Intersection Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dubinsky, Manuel, Chao, Kun-Mao, Massri, César, Taubin, Gabriel
Format:	Preprint
Published:	2024
Subjects:	Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Minimum Spanning Tree Cycle Intersection Problem
by: Dubinsky, Manuel, et al.
Published: (2021)

tinygarden -- A java package for testing properties of spanning trees
by: Dubinsky, Manuel, et al.
Published: (2024)

Three aspects of the MSTCI problem
by: Dubinsky, Manuel, et al.
Published: (2023)

Minimum Spanning Trees with Bounded Degrees of Vertices in a Specified Stable Set
by: Brause, Christoph, et al.
Published: (2022)

Another Way to Lower the Bound for Distinct Squares
by: Tomita, Eitatsu, et al.
Published: (2026)

Improved Lower Bounds on Multiflow-Multicut Gaps
by: Kalantarzadeh, Sina, et al.
Published: (2025)

Lower Bounds for Linear Operators
by: Ko, Young Kun
Published: (2025)

Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees
by: Gerke, Stefanie, et al.
Published: (2024)

Lower Bounds for Induced-Universal Graphs
by: Gavoille, Cyril, et al.
Published: (2025)

Lower Bounds for Maximum Weighted Cut
by: Gutin, Gregory, et al.
Published: (2021)

Weighted Group Search on the Disk & Improved Lower Bounds for Priority Evacuation
by: Georgiou, Konstantinos, et al.
Published: (2024)

Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
by: Veldt, Nate, et al.
Published: (2025)

The Rainbow Arborescence Problem on Cycles
by: Bérczi, Kristóf, et al.
Published: (2025)

Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs
by: Bhyravarapu, Sriram, et al.
Published: (2021)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
by: Wang, Chen, et al.
Published: (2024)

Sparse Bounded Hop-Spanners for Geometric Intersection Graphs
by: Bhore, Sujoy, et al.
Published: (2025)

On the Gap between Hereditary Discrepancy and the Determinant Lower Bound
by: Li, Lily, et al.
Published: (2023)

Finding a Minimum Spanning Tree with a Small Non-Terminal Set
by: Hanaka, Tesshu, et al.
Published: (2023)

The Planted Spanning Tree Problem
by: Moharrami, Mehrdad, et al.
Published: (2025)

Minimum Cut Representability of Stable Matching Problems
by: Faenza, Yuri, et al.
Published: (2025)

Minimum 0-Extension Problems on Directed Metrics
by: Hirai, Hiroshi, et al.
Published: (2020)

A Balancing Theorem for Spanning Trees of Rectangular Grid Graphs
by: Zhang, Jiechen
Published: (2026)

An Algorithm for the Decomposition of Complete Graph into Minimum Number of Edge-disjoint Trees
by: Sinha, Antika, et al.
Published: (2024)

Quantum Approaches to the Minimum Edge Multiway Cut Problem
by: Abbassi, Ali, et al.
Published: (2026)

Cycles of Well-Linked Sets II: an Elementary Bound for the Directed Grid Theorem
by: Hatzel, Meike, et al.
Published: (2026)

Lower Bounds and properties for the average number of colors in the non-equivalent colorings of a graph
by: Hertz, Alain, et al.
Published: (2021)

Flipping Non-Crossing Spanning Trees
by: Bjerkevik, Håvard Bakke, et al.
Published: (2024)

Constrained Flips in Plane Spanning Trees
by: Aichholzer, Oswin, et al.
Published: (2025)

Lower bounds for the integrality gap of the bi-directed cut formulation of the Steiner Tree Problem
by: Bernardelli, Ambrogio Maria, et al.
Published: (2024)

Finding a Sparse Connected Spanning Subgraph in a non-Uniform Failure Model
by: Bentert, Matthias, et al.
Published: (2023)

Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes
by: Asadi, Ali, et al.
Published: (2025)

Branch and Price for the Length-Constrained Cycle Partition Problem
by: Ghannam, Mohammed, et al.
Published: (2024)

Polynomial Kernels for Spanning Tree with Diversity Requirements
by: Golovach, Petr A., et al.
Published: (2026)

Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees
by: Aichholzer, Oswin, et al.
Published: (2026)

The Non-Cancelling Intersections Conjecture
by: Amarilli, Antoine, et al.
Published: (2024)

Computing Lower Bounds on the Nonnegative Rank via Non-Convex Optimization Solvers
by: Baeckelant, Timothy, et al.
Published: (2026)

An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem
by: Xue, Jinghui, et al.
Published: (2024)

Intersecting families with covering number $3$
by: Kupavskii, Andrey
Published: (2024)

Induced Minors and Region Intersection Graphs
by: Bonnet, Édouard, et al.
Published: (2025)

Approximation of Spanning Tree Congestion using Hereditary Bisection
by: Kolman, Petr
Published: (2024)