Cover Image

Query Complexity of the Metric Steiner Tree Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Yu, Khanna, Sanjeev, Tan, Zihan
Format:	Preprint
Published:	2022
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Lower Bounds on $0$-Extension with Steiner Nodes
by: Chen, Yu, et al.
Published: (2024)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
by: Chen, Yu, et al.
Published: (2026)

Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree Problem
by: Bläsius, Thomas, et al.
Published: (2025)

On the Parallel Complexity of Finding a Matroid Basis
by: Khanna, Sanjeev, et al.
Published: (2025)

The Steiner Shortest Path Tree Problem
by: Asher, Omer, et al.
Published: (2025)

The Steiner Path Aggregation Problem
by: Chen, Da Qi, et al.
Published: (2025)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
by: Chuzhoy, Julia, et al.
Published: (2024)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
by: Khanna, Sanjeev, et al.
Published: (2026)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
by: Mahabadi, Sepideh, et al.
Published: (2024)

Simpler O(1) Query Algorithm for Level Ancestors
by: Saxena, Sanjeev
Published: (2022)

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, et al.
Published: (2025)

Sorted Range Reporting and Range Minima Queries
by: Akram, Waseem, et al.
Published: (2021)

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
by: Chekuri, Chandra, et al.
Published: (2024)

A Theory of Spectral CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
by: Khanna, Sanjeev, et al.
Published: (2025)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
by: Assadi, Sepehr, et al.
Published: (2025)

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
by: Assadi, Sepehr, et al.
Published: (2024)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
by: Khanna, Sanjeev, et al.
Published: (2026)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
by: Chuzhoy, Julia, et al.
Published: (2026)

Streaming Maximal Matching with Bounded Deletions
by: Khanna, Sanjeev, et al.
Published: (2025)

A Partition-and-Merge Algorithm for Solving the Steiner Tree Problem in Large Graphs
by: Sun, Ming, et al.
Published: (2022)

Parameterized Algorithms for the Steiner Arborescence Problem on a Hypercube
by: Mahapatra, Sugyani, et al.
Published: (2021)

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
by: Chen, Yu, et al.
Published: (2024)

Multi-Level Steiner Trees
by: Ahmed, Reyan, et al.
Published: (2018)

Efficient Algorithms and New Characterizations for CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2024)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
by: Khanna, Sanjeev, et al.
Published: (2024)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
by: Khanna, Sanjeev, et al.
Published: (2024)

Query-decision Regression between Shortest Path and Minimum Steiner Tree
by: Tong, Guangmo, et al.
Published: (2024)

Lower Bounds on Tree Covers
by: Chen, Yu, et al.
Published: (2025)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
by: Disser, Yann, et al.
Published: (2024)

Top-k Stabbing Interval Queries
by: Akram, Waseem, et al.
Published: (2024)

Prize-Collecting Steiner Tree: A 1.79 Approximation
by: Ahmadi, Ali, et al.
Published: (2024)

Cost-Distance Steiner Trees for Timing-Constrained Global Routing
by: Held, Stephan, et al.
Published: (2025)

Online Steiner Forest with Recourse
by: Long, Yaowei, et al.
Published: (2026)

Terminal Steiner tree problem : Complexity and Algorithms
by: S, Jyothish, et al.
Published: (2026)

The Complexity of Geodesic Spanners using Steiner Points
by: de Berg, Sarita, et al.
Published: (2024)

Optimal Parallel Basis Finding in Graphic and Related Matroids
by: Khanna, Sanjeev, et al.
Published: (2025)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
by: Khanna, Sanjeev, et al.
Published: (2026)