Recent Papers
For all material in conferences and journals, the copyright is owned by
the publisher.
-
``Iterated rounding algorithms for the smallest $k$-edge connected
spanning subgraph,''
H.N. Gabow, S. Gallagher, SODA 08, pp 550-559.
-
"Upper degree-constrained partial orientations",
SODA
06.
-
"On the L_infinity-norm of extreme points for crossing supermodular
directed network LPs",
IPCO 05.
-
"Approximating the smallest k-edge connected spanning subgraph by
LP-rounding", H.N. Gabow, M.X. Goemans, E. Tardos and D.P. Williamson,
SODA 05, pp. 562-571. Complete version:
-
"Finding paths and cycles of superpolylogarithmic length",
STOC 04, pp. 407-416.
-
"Finding a long directed cycle,"
H.N. Gabow and S. Nie,
SODA '04, pp 49-58.
-
"Special edges, and approximating the smallest directed k-edge
connected spanning subgraph,"
H.N. Gabow,
SODA '04, pp 227-236.
-
"Searching",
H.N. Gabow,
book chapter
in
Handbook of Graph Theory, J.L. Gross and J. Yellen eds., pp.953-984,
2003.
-
"Better performance bounds for finding the smallest k-edge connected
spanning subgraph of a multigraph,"
H.N. Gabow.
SODA 03.
-
"An ear decomposition approach to approximating the smallest
3-edge connected
spanning subgraph of a multigraph,"
H.N. Gabow, SIAM J. Disc. Math 18,1, 2004, pp.41-70.
- "The dynamic vertex minimum problem and
its application to
clustering-type approximation algorithms,"
H.N. Gabow and S. Pettie. SWAT '02.
- "Using expander graphs to find vertex connectivity,"
H.N. Gabow.
-
"An algorithm for strongly connected component analysis in n log n
symbolic steps,"
R. Bloem, H.N. Gabow and F. Somenzi,
Int'l Conf. on Formal Methods in Computer-Aided Design 2000
(FMCAD '00).
-
"A network-flow-based scheduler:
design, performance history and experimental analysis,"
H.N. Gabow, T. Kohno,
ALENEX 00.
-
"Incrementing bipartite digraph edge-connectivity,"
H.N. Gabow, T. Jordán,
Journal of Combinatorial Optimization 4,4, 2000, pp.449-486.
-
"Path-based depth-first search for strong and biconnected components,"
Information Processing Letters 74, 2000, pp.107-114.
Note added May 2006: The low level strong components
algorithm was published several years before this by Joseph Cheriyan and
Kurt Mehlhorn:
"Algorithms for Dense Graphs and Networks on the
Random Access Computer",
Algorithmica 15,
1996,
pp.521-549.
This paper does not use the path-based approach, which is the essential
point
of the IPL paper.
The path-based approach to DFS
simplifies most basic DFS algorithms. It is covered in the
above chapter "Searching", and also in this
supplementary material
on DFS.
-
"Computing vertex connectivity: New bounds from old techniques,"
M.R. Henzinger, S. Rao, H.N. Gabow,
Journal of Algorithms 34, 2, 2000, pp. 222-250.
-
"Unique maximum matching algorithms,"
H.N. Gabow, H. Kaplan, R.E. Tarjan.
-
"An RNA folding method capable of identifying pseudoknots and
base triples,"
J.E. Tabaska, R.B. Cary, H.N. Gabow, G.D. Stormo.
Bioinformatics 14 , 8, 1998, pp. 691-699.
- "How to make a square grid framework with cables rigid,"
H.N. Gabow, T. Jordán, to appear in SIAM J. on Computing,
30,2, pp.649-680, 2000.
- "Edge-connectivity augmentation with partition constraints,"
J. Bang-Jensen, H.N. Gabow, T. Jordán, Z. Szigeti.
- "Packing algorithms for arborescences (and spanning trees)
in capacitated graphs,"
H.N. Gabow, K.S. Manu.
Mathematical Programming-B, Vol. 82, 1-2, 1998, pp.83-109.
- "An efficient approximation algorithm for the survivable
network design problem,"
H.N. Gabow, M.X. Goemans, D.P. Williamson.
Mathematical Programming-B, Vol. 82, 1-2, 1998, pp.13-40.