A O( k)-approximation for \textsc{Directed Steiner Tree} in planar graphs

DOI10.1145/3734525MaRDI QIDQ6907341zbMATH OpenFDO

Authors Zachary Friggstad, Ramin Mousavi

Publication date 3 November 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3734525

zbMATH Keywords

approximation algorithmscombinatorial optimizationdirected Steiner tree

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
• A constant-factor approximation for quasi-bipartite directed Steiner tree on minor-free graphs
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• A Separator Theorem for Planar Graphs
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• An 11/6-approximation algorithm for the network Steiner problem
• An O(n n) approximation scheme for Steiner tree in planar graphs
• Applications of a Planar Separator Theorem
• Approximation Algorithms for Directed Steiner Problems
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Bypassing the surface embedding: approximation schemes for network design in minor-free graphs
• Compact oracles for reachability and approximate distances in planar digraphs
• Graph minors. XVI: Excluding a non-planar graph
• New approximation algorithms for the Steiner tree problems
• Node-weighted Steiner tree and group Steiner tree in planar graphs
• Object location using path separators
• Polylogarithmic inapproximability
• Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems
• Steiner tree approximation via iterative randomized rounding
• The polymatroid Steiner problems
• The Steiner problem with edge lengths 1 and 2
• Tighter Bounds for Graph Steiner Tree Approximation

This page was built for publication: A \(O(\log k)\)-approximation for \textsc{Directed Steiner Tree} in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6907341)