Harold N. Gabow

Harold N. Gabow is a computer scientist known for research on combinatorial algorithms, graph algorithms and data structures. He is a Professor Emeritus at the University of Colorado Boulder, and founding Editor-in-Chief of ACM Transactions on Algorithms.

Harold N. Gabow
Nationality	American
Education	Harvard University (B.A., 1968) Stanford University (Ph.D., 1973)
Occupation	Computer Scientist
Known for	Research on combinatorial algorithms, graph algorithms, and data structures
Spouse	Patricia Anne Acquaviva ​ ​ (m. 1971)​

Education and career

Gabow graduated from Martin Van Buren High School, where he was mentored by Ira Ewen.^[1] He graduated summa cum laude from Harvard University in 1968, with a bachelor's degree in mathematics.^[2] He completed his Ph.D. in computer science in 1973 at Stanford University; his dissertation, Implementations of algorithms for maximum matching on nonbipartite graphs, was supervised by Harold S. Stone.^[2][3]

After working as an instructor at the University of Pennsylvania for a year, he joined the University of Colorado Boulder faculty in 1973 as an Assistant Professor of Computer Science, becoming Associate Professor in 1979, Full Professor in 1986, Professor Emeritus in 2008.^[2]

Gabow was the founding Editor-in-Chief of ACM Transactions on Algorithms (TALG), which published its first issue in 2005, after the mass resignation of the editorial board of its predecessor, Elsevier's Journal of Algorithms.^[4] He stepped down as Editor-in-Chief on his retirement in 2008.^[2]

Selected publications

``A linear-time algorithm for a special case of disjoint set union,'' H.N. Gabow and R.E. Tarjan, Journal of Computer and System Sciences 30, 2, 1985, 209-221.

``Scaling algorithms for network problems,'' H.N. Gabow, Journal of Computer and System Sciences 31, 2, 1985, 148-168.

``Faster scaling algorithms for general graph matching problems,'' H.N. Gabow and R.E. Tarjan, Journal of the ACM 38, 4, 1991, 815-853.

``A matroid approach to finding edge connectivity and packing arborescences,'' H.N. Gabow, Journal of Computer and System Sciences 50, 2, 1995, 259-273.

``Path-based depth-first search for strong and biconnected components,'' H.N. Gabow, Information Processing Letters 74, 2000, 107-114.

"The weighted matching approach to maximum cardinality matching," H.N. Gabow, Fundamenta Informaticae (Elegant Structures in Computation:To Andrzej Ehrenfeucht on His 85th Birthday 154, 1-4, 2017, 109-130.

"Data structures for weighted matching and extensions to b-matching and f-factors," H.N. Gabow, ACM Transactions on Algorithms14, 3, 2018, Article 39, 80 pages.

``Maximum cardinality f-matching in time O(n^2/3m),'' H.N. Gabow, ACM Transactions on Algorithms 21, 1, 2025, Article 9, 28 pages.

Recognition

Gabow was named as an ACM Fellow in 2002, "for contributions to efficient algorithms to flows, connectivity and matching".^[5] With co-authors M. Goemans, E. Tardos and D. Williamson he won the 2009 Glover-Klingman Prize for best paper of the year in Networks: An International Journal. He was awarded the SIGACT Distinguished Service Prize in 2010.

Personal life

Gabow is married to physician and healthcare executive Patricia A. Gabow.^[6]