Buchumschlag

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chekuri, Chandra, Jain, Rhea
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

Node-Weighted Multicut in Planar Digraphs
von: Chekuri, Chandra, 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)

Approximation Algorithms for Network Design in Non-Uniform Fault Models
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Approximation Algorithms for Hop Constrained and Buy-at-Bulk Network Design via Hop Constrained Oblivious Routing
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Streaming Algorithms for Network Design
von: Chekuri, Chandra, et al.
Veröffentlicht: (2025)

On Sparsest Cut and Conductance in Directed Polymatroidal Networks
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Colorful Priority $k$-Supplier
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

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

Polylogarithmic Approximation for Robust s-t Path
von: Li, Shi, et al.
Veröffentlicht: (2023)

Steiner Forest: A Simplified Better-Than-2 Approximation
von: Gupta, Anupam, et al.
Veröffentlicht: (2025)

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

On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
von: Chandrasekaran, Karthekeyan, et al.
Veröffentlicht: (2025)

Fully Dynamic Strongly Connected Components in Planar Digraphs
von: Karczmarz, Adam, et al.
Veröffentlicht: (2024)

Hardness and Approximation for Coloring Digraphs
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2026)

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
von: Ahmadi, Ali, et al.
Veröffentlicht: (2025)

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

Approximation Algorithms for Digraph Width Parameters
von: Kintali, Shiva, et al.
Veröffentlicht: (2011)

Exponential Time Approximation for Coloring 3-Colorable Graphs
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

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

Hedgegraph Polymatroids
von: Chandrasekaran, Karthekeyan, et al.
Veröffentlicht: (2025)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
von: Agarwal, Arpit, et al.
Veröffentlicht: (2024)

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

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
von: Das, Debarati, et al.
Veröffentlicht: (2026)

Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
von: Harb, Elfarouk, et al.
Veröffentlicht: (2025)

Hypergraph Splitting-Off via Element-Connectivity Preserving Reductions
von: Chandrasekaran, Karthekeyan, et al.
Veröffentlicht: (2025)

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

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
von: Koh, Zhuan Khye, et al.
Veröffentlicht: (2024)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
von: Anand, Aditya, et al.
Veröffentlicht: (2025)

Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
von: Chandrasekaran, Karthekeyan, et al.
Veröffentlicht: (2023)

Memory Reallocation with Polylogarithmic Overhead
von: Jin, Ce
Veröffentlicht: (2026)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
von: Bhore, Sujoy, et al.
Veröffentlicht: (2024)

Sublinear Metric Steiner Forest via Maximal Independent Set
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2025)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
von: Włodarczyk, Michał
Veröffentlicht: (2024)

Prize-Collecting Steiner Tree: A 1.79 Approximation
von: Ahmadi, Ali, et al.
Veröffentlicht: (2024)

A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays
von: Dufay, Marc, et al.
Veröffentlicht: (2025)

On the Bidirected Cut Relaxation for Steiner Forest
von: Byrka, Jarosław, et al.
Veröffentlicht: (2024)

Dynamic Longest Common Substring in Polylogarithmic Time
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2020)

On Thin Perfect Matchings up to Polylogarithmic Factors
von: Haqi, Alireza, et al.
Veröffentlicht: (2026)

Polylogarithmic Approximation for Covering and Connecting Multi-Interface Networks
von: Szyfelbein, Michał, et al.
Veröffentlicht: (2026)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
von: Kalavas, Andreas, et al.
Veröffentlicht: (2025)