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.