Hal Gabow

         Professor Emeritus

• Email: hal at cs dot colorado dot edu
• Vita

• Research. My research is in the design and analysis of algorithms (especially graph algorithms), combinatorial optimization and linear programming.
  • Most recent papers
    • Maximum Cardinality $f$-Matching in Time $O(n^{2/3}m)$. 28 pages. Extends the bound for simple graphs from the bipartite case, known since 1973, to general graphs.
      H.N. Gabow
      ACM Transactions on Algorithms 2025
    • Blocking Trails for $f$-factors of Multigraphs, 46 pages. A linear time subroutine to speed up algorithms for f-matching problems (e.g., maximum cardinality, maximum weight).
      H.N. Gabow
      Algorithmica 2023
    • A Weight-Scaling Algorithm for f-factors of Multigraphs, 76 pages. A more concrete development of the matching algorithm of Gabow and Tarjan (1989), extended to f-factors, modified by a new blossom structure "e-blossoms".
      H.N. Gabow
      Algorithmica 2023
    • Algorithms for weighted matching generalizations I: Bipartite graphs, $b$-matching, and unweighted $f$-factors
      Algorithms for weighted matching generalizations II: $f$-factors and the special case of shortest paths
      H.N. Gabow and P. Sankowski
      SIAM J. on Computing, 2021
      This two-part paper culminates in an efficient algebraic algorithm for finding a maximum weight $f$-matching of a multigraph. A special case is finding a shortest path in an undirected graph with possibly negative edges. A representation for single-source shortest-paths in undirected graphs is presented, generalizing the standard shortest-path tree to a “tree of cycles”.
    • The first part of this article presents a data structure for weighted matching in time O(n(m+n log n)). Then we extend this to arbitrary degree constraints. (This entails first defining blossoms, and then giving simple algorithms for maximum weight b-matchings and f-factors.)
      
      Data Structures for Weighted Matching and Extensions to b-matching and f-factors

      Harold N. Gabow
      ACM Transactions on Algorithms (TALG), 2018
    • The weighted matching approach to maximum cardinality matching, 18 pages. A complete algorithm for nonbipartite matching in time O( √n m). Appendix shows the approach can give a simple correctness proof for the Micali-Vazirani matching algorithm. Also includes a detailed correctness proof of the DFS alternative to the MV DDFS algorithm.
      reference: Fundamenta Informaticae (Elegant Structures in Computation: To Andrzej Ehrenfeucht on His 85th Birthday) 154, 1-4, 2017, pp. 109-130.
    • This article presents a data structure used in the above TALG weighted matching algorithm. It also simplifies the implementation of the static/incremental-tree set merging data structure of Gabow and Tarjan (1985).
      
      A Data Structure for Nearest Common Ancestors with Linking

      Harold N. Gabow
      ACM Transactions on Algorithms (TALG), 2017
    • Set-merging for the Matching Algorithm of Micali and Vazirani, 6 pages.
    • A combinatoric interpretation of dual variables for weighted matching problems , 37 pages.
    • The minset poset is well-known. We show it gives the cactus representation and the dominator tree:
      The Minset-Poset Approach to Representations of Graph Connectivity

      Harold N. Gabow
      ACM Transactions on Algorithms (TALG), 2016
  • Older papers

• Teaching.
  • Path-based depth first search    (Why path-based dfs?)
  • Class notes for CS5654: Linear Programming (Fall 2007, 220 pages)
  • More on Teaching

• Service. (not much in retirement)
  • TALG history.
  • My SODA 2007 Program Committee report (the stats are old but the lessons learned are timeless)

• Personal.
  • A list of my favorite things.
  • Some pics

  Home - Return to CS Dept Home Page

  ---