Demo Data from VLDB 2026 / reviewers in the wild / expert
Suzanne Gallagher
dblp:29/6252
· DBLP profile ↗
2ranked-venue papers
0as first author
0since 2021 · last 2012
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
2 papers |
Approximation and online algorithms · 70% Graph algorithms and graph theory · 30% |
Topics — the 6 heaviest of 6, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Approximation and online algorithms › approximation algorithms › network design
survivable network design |
0.2 | 2 | 2012 | Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph · SIAM J. Comput. 2012 Iterated rounding algorithms for the smallest k-edge connected spanning subgraph · SODA 2008 |
Graph algorithms and graph theory
graph connectivity |
0.1 | 1 | 2012 | Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph · SIAM J. Comput. 2012 |
Approximation and online algorithms › approximation algorithms › network design
network design approximation |
0.1 | 1 | 2012 | Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph · SIAM J. Comput. 2012 |
Graph algorithms and graph theory › graph connectivity
edge connectivity |
0.1 | 1 | 2008 | Iterated rounding algorithms for the smallest k-edge connected spanning subgraph · SODA 2008 |
Approximation and online algorithms › approximation algorithms › network design › survivable network design
k-edge-connected spanning subgraph |
0.1 | 1 | 2008 | Iterated rounding algorithms for the smallest k-edge connected spanning subgraph · SODA 2008 |
Approximation and online algorithms › approximation algorithms
network design |
0.1 | 1 | 2008 | Iterated rounding algorithms for the smallest k-edge connected spanning subgraph · SODA 2008 |
Methods — techniques the papers use, named apart from their topics
linear programming rounding · 0.2iterated rounding · 0.2
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2012 | Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning SubgraphabstractWe present the best known algorithms for approximating the minimum-size undirected k-edge connected spanning subgraph. For simple graphs our approximation ratio is $1+ {1}/(2k) + O({1}/{k^2})$. The more precise version of this bound requires $k\ge 7$, and for all such k it improves the long-standing performance ratio of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528–560], $1+2/(k+1)$. The improvement comes in two steps. First we show that for simple k-edge connected graphs, any laminar family of degree k sets is smaller than the general bound ($n(1+ {3}/{k} + O(1/k\sqrt k))$ versus $2n$). This immediately implies that iterated rounding improves the performance ratio of Cheriyan and Thurimella. The second step carefully chooses good edges for rounding. For multigraphs our approximation ratio is $1+(21/11)k <1+1.91/k$ for any $k>1$. This improves the previous ratio $1+2/k$ [H. N. Gabow, M. X. Goemans, E. Tardos, and D. P. Williamson, Networks, 53 (2009), pp. 345–357]. It is of interest since it is known that for some constant $c>0$, an approximation ratio $\le 1+c/k$ implies $P=NP$. Our approximation ratio extends to the minimum-size Steiner network problem, where k denotes the average vertex demand. The algorithm exploits rounding properties of the first two linear programs in iterated rounding. Harold N. Gabow, Suzanne Gallagher |
SIAM J. Comput. | 2 |
| 2008 | Iterated rounding algorithms for the smallest k-edge connected spanning subgraph
Harold N. Gabow, Suzanne Gallagher |
SODA | 2 |