Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DIRECTED GRAPHS:
Reports tagged with Directed graphs:
TR07-120 | 5th October 2007
Sharon Feldman, Guy Kortsarz, Zeev Nutov

Improved approximation algorithms for directed Steiner forest

We consider the k-Directed Steiner Forest} (k-dsf) problem:
given a directed graph G=(V,E) with edge costs, a collection D subseteq V \times V
of ordered node pairs, and an integer k leq |D|, find a minimum cost subgraph
H of G
that contains an st-path for (at least) k ... more >>>




ISSN 1433-8092 | Imprint