Improved Approximation Algorithm for Steiner k -Forest with Nearly Uniform Weights

DOI10.1145/3077581MaRDI QIDQ4554929zbMATH OpenOpenAlexFDO

Authors Michael Dinitz, Guy Kortsarz, Zeev Nutov

Publication date 12 November 2018

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

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

zbMATH Keywords

dial-a-rideminimum \(k\)-edge subgraph

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06) Programming involving graphs or networks (90C35)

Recommendations

• Improved approximation algorithm for Steiner k-Forest with nearly uniform weights
• An Approximation Algorithm to the k-Steiner Forest Problem
• An approximation algorithm to the \(k\)-Steiner forest problem
• Improved approximating algorithms for directed Steiner forest
• Improved approximation algorithms for directed Steiner forest
• Approximation algorithms for Steiner forest: An experimental study
• An improved approximation algorithm for the uniform cost-distance Steiner tree problem
• Improved Approximations for the Steiner Tree Problem
• scientific article; zbMATH DE number 742979
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees

Cited in

(4)

• Improved approximation algorithm for Steiner k-Forest with nearly uniform weights
• Dial a Ride from k-Forest
• Dial a ride from k-forest
• The strongish planted clique hypothesis and its consequences

This page was built for publication: Improved Approximation Algorithm for Steiner k -Forest with Nearly Uniform Weights

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