首页 | 本学科首页   官方微博 | 高级检索  
     


A practical greedy approximation for the directed Steiner tree problem
Authors:Dimitri Watel  Marc-Antoine Weisser
Affiliation:1.CEDRIC-CNAM 292 rue Saint-Martin,Paris Cédex 03,France;2.LRI, CentraleSupélec,Université Paris-Saclay,Orsay Cedex,France
Abstract:The directed Steiner tree (DST) NP-hard problem asks, considering a directed weighted graph with n nodes and m arcs, a node r called root and a set of k nodes X called terminals, for a minimum cost directed tree rooted at r spanning X. The best known polynomial approximation ratio for DST is a (O(k^varepsilon ))-approximation greedy algorithm. However, a much faster k-approximation, returning the shortest paths from r to X, is generally used in practice. We give two new algorithms : a fast k-approximation called Greedy(_text {FLAC}) running in (O(m log (n)k + min (m, nk)nk^2)) and a (O(sqrt{k}))-approximation called Greedy(_text {FLAC}^triangleright ) running in (O(nm + n^2 log (n)k +n^2 k^3)). We provide computational results to show that, Greedy(_text {FLAC}) rivals in practice with the running time of the fast k-approximation and returns solution with smaller cost in practice.
Keywords:
本文献已被 SpringerLink 等数据库收录!
正在获取相似文献,请稍候...
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号