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
The first part of this article presents a data structure for weighted matching in time
O
(
n
(
m+n
log
n
)).
Data Structures for Weighted Matching and Extensions to
b
-matching and
f
-factors
Harold N. Gabow
ACM Transactions on Algorithms (TALG), 2018
frames are not supported
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.
This article presents a data structure used in the above weighted matching algorithm.
A Data Structure for Nearest Common Ancestors with Linking
Harold N. Gabow
ACM Transactions on Algorithms (TALG), 2017
frames are not supported
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
frames are not supported
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