Email: hal at cs dot colorado dot edu
My research is in the design and analysis of algorithms (especially graph algorithms), combinatorial optimization and linear programming.
Most recent papers (send email for a copy)
The weighted matching approach to maximum cardinality matching,
18 pages. A
algorithm for nonbipartite matching in time
). Appendix shows the approach can give a simple correctness proof for the Micali-Vazirani matching algorithm.
Data Structures for Weighted Matching and Extensions to b-matching and f-factors
A Data Structure for Nearest Common Ancestors with Linking
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, 78 pages.
Path-based depth first search
(Why path-based dfs?)
Class notes for CS5654:
(Fall 2007, 220 pages)
(not much in retirement)
My SODA 2007
Program Committee report
(the stats are old but the lessons learned are timeless)
A list of
my favorite things.
- Return to CS Dept Home Page