Buchumschlag

Lower Bounds on $0$-Extension with Steiner Nodes

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chen, Yu, Tan, Zihan
Format:	Preprint
Veröffentlicht:	2024
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

Lower Bounds on Flow Sparsifiers with Steiner Nodes
von: Chen, Yu, et al.
Veröffentlicht: (2026)

Lower Bounds on Tree Covers
von: Chen, Yu, et al.
Veröffentlicht: (2025)

Query Complexity of the Metric Steiner Tree Problem
von: Chen, Yu, et al.
Veröffentlicht: (2022)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
von: Feldmann, Andreas Emil, et al.
Veröffentlicht: (2024)

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
von: Chen, Yu, et al.
Veröffentlicht: (2024)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2024)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
von: D'Angelo, Gianlorenzo, et al.
Veröffentlicht: (2025)

The Steiner Path Aggregation Problem
von: Chen, Da Qi, et al.
Veröffentlicht: (2025)

The Bidirected Cut Relaxation for Steiner Tree: Better Integrality Gap Bounds and the Limits of Moat Growing
von: Paschmanns, Paul, et al.
Veröffentlicht: (2026)

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
von: Yoshida, Yuichi
Veröffentlicht: (2026)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Multi-Level Steiner Trees
von: Ahmed, Reyan, et al.
Veröffentlicht: (2018)

Online Steiner Forest with Recourse
von: Long, Yaowei, et al.
Veröffentlicht: (2026)

New Algorithms and Lower Bounds for Streaming Tournaments
von: Ghosh, Prantar, et al.
Veröffentlicht: (2024)

Double Exponential Lower Bound for Telephone Broadcast
von: Tale, Prafullkumar
Veröffentlicht: (2024)

Dynamic PageRank: Algorithms and Lower Bounds
von: Jayaram, Rajesh, et al.
Veröffentlicht: (2024)

Fine Grained Lower Bounds for Multidimensional Knapsack
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2024)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
von: Cheng, Yu, et al.
Veröffentlicht: (2024)

Optimal Sensitivity Oracle for Steiner Mincut
von: Bhanja, Koustav
Veröffentlicht: (2024)

Graph Spanners for Group Steiner Distances
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

The Steiner Shortest Path Tree Problem
von: Asher, Omer, et al.
Veröffentlicht: (2025)

Approximation Algorithms for Steiner Connectivity Augmentation
von: Hathcock, Daniel, et al.
Veröffentlicht: (2023)

Streaming Algorithms for Geometric Steiner Forest
von: Czumaj, Artur, et al.
Veröffentlicht: (2020)

DAG Covers: The Steiner Point Effect
von: Bhore, Sujoy, et al.
Veröffentlicht: (2026)

A Lower Bound for Light Spanners in General Graphs
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
von: Funke, Daniel, et al.
Veröffentlicht: (2024)

Improved Lower Bounds for Privacy under Continual Release
von: Aryanfard, Bardiya, et al.
Veröffentlicht: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
von: Fleming, Noah, et al.
Veröffentlicht: (2026)

Lower Bounds for Non-adaptive Local Computation Algorithms
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
von: Huiberts, Sophie, et al.
Veröffentlicht: (2022)

2-Approximation for Prize-Collecting Steiner Forest
von: Ahmadi, Ali, et al.
Veröffentlicht: (2023)

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
von: Manea, Florin, et al.
Veröffentlicht: (2024)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

Improved Lower Bounds on the Expected Length of Longest Common Subsequences
von: Heineman, George T., et al.
Veröffentlicht: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
von: Chitnis, Rajesh, et al.
Veröffentlicht: (2024)

A Tight Lower Bound for Cycle Detection in Grid Graphs
von: Au, Andrew
Veröffentlicht: (2026)

Tight Lower Bounds for Central String Queries in Compressed Space
von: Kempa, Dominik, et al.
Veröffentlicht: (2025)

Tight Static Lower Bounds for Non-Adaptive Data Structures
von: Persiano, Giuseppe, et al.
Veröffentlicht: (2020)

Lower Bounds for Matroid Optimization Problems with a Linear Constraint
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2023)