Buchumschlag

Budget and Profit Approximations for Spanning Tree Interdiction

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ostrovsky, Rafail, Rabani, Yuval, Tov, Yoav Siman
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

New Results on a General Class of Minimum Norm Optimization Problems
von: Chen, Kuowen, et al.
Veröffentlicht: (2025)

A Note on Interdiction of Linear Minimization Problems
von: Cong, Yu, et al.
Veröffentlicht: (2026)

A Reduction-based Algorithm for the Clique Interdiction Problem
von: Zhu, Chenghao, et al.
Veröffentlicht: (2025)

Exact Clique Number Manipulation via Edge Interdiction
von: Zhou, Yi, et al.
Veröffentlicht: (2026)

Approximate Spanning Tree Counting from Uncorrelated Edge Sets
von: Liu, Yang P., et al.
Veröffentlicht: (2025)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
von: Abbasi, Ali, et al.
Veröffentlicht: (2026)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
von: Çivril, Ali
Veröffentlicht: (2023)

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

On Approximability of $\ell_2^2$ Min-Sum Clustering
von: S., Karthik C., et al.
Veröffentlicht: (2024)

Approximation of Spanning Tree Congestion using Hereditary Bisection
von: Kolman, Petr
Veröffentlicht: (2024)

Interdiction of minimum spanning trees and other matroid bases
von: Weninger, Noah, et al.
Veröffentlicht: (2024)

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

Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
von: Hellerstein, Lisa, et al.
Veröffentlicht: (2026)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
von: Norose, Ryoma, et al.
Veröffentlicht: (2024)

Online Disjoint Spanning Trees and Polymatroid Bases
von: Chandrasekaran, Karthekeyan, et al.
Veröffentlicht: (2025)

Planar Length-Constrained Minimum Spanning Trees
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2025)

Spanning and Metric Tree Covers Parameterized by Treewidth
von: Elkin, Michael, et al.
Veröffentlicht: (2025)

Simple Length-Constrained Minimum Spanning Trees
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2024)

Stochastic Minimum Spanning Trees with a Single Sample
von: Hoeksma, Ruben, et al.
Veröffentlicht: (2024)

Two Complexity Results on Spanning-Tree Congestion Problems
von: Atalig, Sunny, et al.
Veröffentlicht: (2026)

Enumerating All Directed Spanning Trees in Optimal Time
von: Gawrychowski, Paweł, et al.
Veröffentlicht: (2026)

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

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
von: Peng, Pan, et al.
Veröffentlicht: (2026)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Approximation Algorithms for Budget Splitting in Multi-Channel Influence Maximization
von: Ali, Dildar, et al.
Veröffentlicht: (2026)

Finding Spanning Trees with Perfect Matchings
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
von: Ding, Xiangyun, et al.
Veröffentlicht: (2025)

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

Time, Message and Memory-Optimal Distributed Minimum Spanning Tree and Partwise Aggregation
von: Goldenfeld, Michael Elkin Tanya
Veröffentlicht: (2026)

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

Online Algorithms with Randomly Infused Advice
von: Emek, Yuval, et al.
Veröffentlicht: (2023)

Above-Guarantee Algorithm for Properly Colored Spanning Trees
von: Bai, Yuhang, et al.
Veröffentlicht: (2026)

Spanning tree congestion of proper interval graphs
von: Otachi, Yota
Veröffentlicht: (2026)

Adwords with Unknown Budgets and Beyond
von: Udwani, Rajan
Veröffentlicht: (2021)

Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
von: Veldt, Nate, et al.
Veröffentlicht: (2025)

Designing Approximate Binary Trees for Trees
von: Kellerhals, Leon, et al.
Veröffentlicht: (2026)

Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism
von: Karamchedu, Mithra, et al.
Veröffentlicht: (2025)

A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors
von: Liang, Wei, et al.
Veröffentlicht: (2024)

Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs
von: Gil, Yuval
Veröffentlicht: (2024)

Quantum Speedup for Sampling Random Spanning Trees
von: Apers, Simon, et al.
Veröffentlicht: (2025)