Cover Image

DAG Covers: The Steiner Point Effect

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhore, Sujoy, Chang, Hsien-Chih, Conroy, Jonathan, Filtser, Arnold, Oh, Eunjin, Wein, Nicole, Zheng, Da Wei
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Dynamic Light Spanners in Doubling Metrics
by: Bhore, Sujoy, et al.
Published: (2026)

How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs
by: Conroy, Jonathan, et al.
Published: (2025)

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
by: Bhore, Sujoy, et al.
Published: (2023)

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

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
by: Bhore, Sujoy, et al.
Published: (2024)

Stochastic Embedding of Digraphs into DAGs
by: Filtser, Arnold
Published: (2025)

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
by: Filtser, Arnold
Published: (2024)

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
by: Bhore, Sujoy, et al.
Published: (2025)

Distance Approximating Minors for Planar and Minor-Free Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Scattering and Sparse Partitions, and their Applications
by: Filtser, Arnold
Published: (2020)

Hop-Constrained Metric Embeddings and their Applications
by: Filtser, Arnold
Published: (2021)

A face cover perspective to $\ell_1$ embeddings of planar graphs
by: Filtser, Arnold
Published: (2019)

On Strong Diameter Padded Decompositions
by: Filtser, Arnold
Published: (2019)

FPT approximations for Capacitated Sum of Radii and Diameters
by: Filtser, Arnold, et al.
Published: (2024)

Clustering under Constraints: Efficient Parameterized Approximation Schemes
by: Bhore, Sujoy, et al.
Published: (2025)

Light Spanners with Small Hop-Diameter
by: Bhore, Sujoy, et al.
Published: (2025)

Online TCP Acknowledgment under General Delays
by: Bhore, Sujoy, et al.
Published: (2026)

Highway Dimension: a Metric View
by: Feldmann, Andreas Emil, et al.
Published: (2024)

O(1)-Distortion Planar Emulators for String Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

Visibility Queries in Simple Polygons
by: Bhore, Sujoy, et al.
Published: (2026)

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, et al.
Published: (2025)

Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates
by: Park, Seongbin, et al.
Published: (2026)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

Mimicking Networks for Constrained Multicuts in Hypergraphs
by: Cho, Kyungjin, et al.
Published: (2024)

Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems
by: Bhore, Sujoy, et al.
Published: (2026)

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
by: Danait, Ved, et al.
Published: (2025)

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

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
by: An, Shinwoo, et al.
Published: (2024)

Improved Online Sorting
by: Nirjhor, Jubayer, et al.
Published: (2025)

Closing the Gap Between Directed Hopsets and Shortcut Sets
by: Bernstein, Aaron, et al.
Published: (2022)

Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes
by: Filtser, Arnold, et al.
Published: (2026)

Settling Weighted Token Swapping up to Algorithmic Barriers
by: Wein, Nicole, et al.
Published: (2025)

Dynamic and Streaming Algorithms for Union Volume Estimation
by: Bhore, Sujoy, et al.
Published: (2026)

Max Cut with Small-Dimensional SDP Solutions
by: Chang, Hsien-Chih, et al.
Published: (2026)

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

Edge-Minimum Walk of Modular Length in Polynomial Time
by: Amarilli, Antoine, et al.
Published: (2024)

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
by: Chen, Kuowen, et al.
Published: (2025)

Are there graphs whose shortest path structure requires large edge weights?
by: Bernstein, Aaron, et al.
Published: (2023)

Single-Source Shortest Path Problem in Weighted Disk Graphs
by: An, Shinwoo, et al.
Published: (2025)