Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Suzanne Gallagher

dblp:29/6252 · DBLP profile ↗
← Back
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

TopicWeightPapersLastEvidence papers
Approximation and online algorithms › approximation algorithms › network design
survivable network design
0.222012
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.112012
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.112012
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.112008
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.112008
Iterated rounding algorithms for the smallest k-edge connected spanning subgraph · SODA 2008
Approximation and online algorithms › approximation algorithms
network design
0.112008
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
YearPublicationVenuePosition
2012 Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph
abstract
We 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
SODA2