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 >>>

We consider <i>minimum equivalent digraph</i> (<i>directed network</i>) problem (also known as the <i>strong transitive reduction</i>), its maximum optimization variant, and some extensions of those two types of problems. We prove the existence of polynomial time approximation algorithms with ratios 1.5 for all the minimization problems and 2 for all the ... more >>>

We study the problem of testing the expansion of
graphs with bounded degree d in sublinear time. A graph is said to
be an \alpha-expander if every vertex set U \subset V of size at
most |V|/2 has a neighborhood of size at least \alpha|U|.

We show that the algorithm ... more >>>