We study the problem of maximizing a monotone non-decreasing function $$f$$f subject to a matroid constraint. Fisher, Nemhauser and Wolsey have shown that, if $$f$$f is submodular, the greedy algorithm will find a solution with value at least $$\frac{1}{...
The diameter and the radius of a graph are fundamental topological parameters that have many important practical applications in real world networks. The fastest combinatorial algorithm for both parameters works by solving the all-pairs shortest paths ...
For an undirected and weighted graph G=(V,E) and a terminal set S\subseteq V, the 2-connected Steiner minimal network (SMN) problem requires to compute a minimum-weight subgraph of G in which all terminals are 2-connected to each other. This problem has ...
Association for Computing Machinery
New York, NY, United States
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in