Cover Image

Budget and Profit Approximations for Spanning Tree Interdiction

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ostrovsky, Rafail, Rabani, Yuval, Tov, Yoav Siman
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

New Results on a General Class of Minimum Norm Optimization Problems
by: Chen, Kuowen, et al.
Published: (2025)

A Note on Interdiction of Linear Minimization Problems
by: Cong, Yu, et al.
Published: (2026)

A Reduction-based Algorithm for the Clique Interdiction Problem
by: Zhu, Chenghao, et al.
Published: (2025)

Exact Clique Number Manipulation via Edge Interdiction
by: Zhou, Yi, et al.
Published: (2026)

Approximate Spanning Tree Counting from Uncorrelated Edge Sets
by: Liu, Yang P., et al.
Published: (2025)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
by: Abbasi, Ali, et al.
Published: (2026)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
by: Çivril, Ali
Published: (2023)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2026)

On Approximability of $\ell_2^2$ Min-Sum Clustering
by: S., Karthik C., et al.
Published: (2024)

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

Interdiction of minimum spanning trees and other matroid bases
by: Weninger, Noah, et al.
Published: (2024)

A $\frac{4}{3}$-Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs
by: Neuwohner, Meike
Published: (2024)

Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
by: Hellerstein, Lisa, et al.
Published: (2026)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
by: Norose, Ryoma, et al.
Published: (2024)

Online Disjoint Spanning Trees and Polymatroid Bases
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Planar Length-Constrained Minimum Spanning Trees
by: Hershkowitz, D Ellis, et al.
Published: (2025)

Spanning and Metric Tree Covers Parameterized by Treewidth
by: Elkin, Michael, et al.
Published: (2025)

Simple Length-Constrained Minimum Spanning Trees
by: Hershkowitz, D Ellis, et al.
Published: (2024)

Stochastic Minimum Spanning Trees with a Single Sample
by: Hoeksma, Ruben, et al.
Published: (2024)

Two Complexity Results on Spanning-Tree Congestion Problems
by: Atalig, Sunny, et al.
Published: (2026)

Enumerating All Directed Spanning Trees in Optimal Time
by: Gawrychowski, Paweł, et al.
Published: (2026)

Parameterized Algorithms for Spanning Tree Isomorphism by Redundant Set Size
by: Shen, Fangjian, et al.
Published: (2025)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
by: Peng, Pan, et al.
Published: (2026)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
by: Azarmehr, Amir, et al.
Published: (2024)

Approximation Algorithms for Budget Splitting in Multi-Channel Influence Maximization
by: Ali, Dildar, et al.
Published: (2026)

Finding Spanning Trees with Perfect Matchings
by: Bérczi, Kristóf, et al.
Published: (2024)

New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
by: Ding, Xiangyun, et al.
Published: (2025)

FAMST: Fast Approximate Minimum Spanning Tree Construction for Large-Scale and High-Dimensional Data
by: Almansoori, Mahmood K. M., et al.
Published: (2025)

Time, Message and Memory-Optimal Distributed Minimum Spanning Tree and Partwise Aggregation
by: Goldenfeld, Michael Elkin Tanya
Published: (2026)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

Online Algorithms with Randomly Infused Advice
by: Emek, Yuval, et al.
Published: (2023)

Above-Guarantee Algorithm for Properly Colored Spanning Trees
by: Bai, Yuhang, et al.
Published: (2026)

Spanning tree congestion of proper interval graphs
by: Otachi, Yota
Published: (2026)

Adwords with Unknown Budgets and Beyond
by: Udwani, Rajan
Published: (2021)

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

Designing Approximate Binary Trees for Trees
by: Kellerhals, Leon, et al.
Published: (2026)

Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism
by: Karamchedu, Mithra, et al.
Published: (2025)

A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors
by: Liang, Wei, et al.
Published: (2024)

Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs
by: Gil, Yuval
Published: (2024)

Quantum Speedup for Sampling Random Spanning Trees
by: Apers, Simon, et al.
Published: (2025)