Harold N. Gabow

136 papers A* 39A 1B 7Misc 1Journal 84Unranked 2
YearRankTypeTitle / Venue / Authors
2025 J jnl
Maximum Cardinality
ACM Trans. Algorithms
Harold N. Gabow
2023 J jnl
A Weight-Scaling Algorithm for f-Factors of Multigraphs.
Algorithmica
Harold N. Gabow
2023 J jnl
Blocking Trails for f-factors of Multigraphs.
Algorithmica
Harold N. Gabow
2023 J jnl
Maximum Cardinality f-Matching in Time O(n
CoRR
Harold N. Gabow
2021 J jnl
Algorithms for Weighted Matching Generalizations I: Bipartite Graphs,
SIAM J. Comput.
Harold N. Gabow, Piotr Sankowski
2021 J jnl
Algorithms for Weighted Matching Generalizations II:
SIAM J. Comput.
Harold N. Gabow, Piotr Sankowski
2021 J jnl
Blocking Trails for f-factors of Multigraphs.
CoRR
Harold N. Gabow
2020 J jnl
A Weight-scaling Algorithm for f-factors of Multigraphs.
CoRR
Harold N. Gabow
2018 J jnl
Data Structures for Weighted Matching and Extensions to
ACM Trans. Algorithms
Harold N. Gabow
2017 J jnl
A Data Structure for Nearest Common Ancestors with Linking.
ACM Trans. Algorithms
Harold N. Gabow
2017 J jnl
The Weighted Matching Approach to Maximum Cardinality Matching.
CoRR
Harold N. Gabow
2017 J jnl
The Weighted Matching Approach to Maximum Cardinality Matching.
Fundam. Informaticae
Harold N. Gabow
2016 J jnl
A Data Structure for Nearest Common Ancestors with Linking.
CoRR
Harold N. Gabow
2016 J jnl
Data Structures for Weighted Matching and Extensions to $b$-matching and $f$-factors.
CoRR
Harold N. Gabow
2016 J jnl
The Minset-Poset Approach to Representations of Graph Connectivity.
ACM Trans. Algorithms
Harold N. Gabow
2015 J jnl
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter, and Matchings.
J. ACM
Marek Cygan, Harold N. Gabow, Piotr Sankowski
2015 J jnl
Set-merging for the Matching Algorithm of Micali and Vazirani.
CoRR
Harold N. Gabow
2014 J jnl
A Model for Minimizing Active Processor Time.
Algorithmica
Jessica Chang, Harold N. Gabow, Samir Khuller
2013 A* conf
Algebraic Algorithms for B-Matching, Shortest Undirected Paths, and F-Factors.
FOCS
Harold N. Gabow, Piotr Sankowski
2013 J jnl
Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors
CoRR
Harold N. Gabow, Piotr Sankowski
2012 J jnl
A Model for Minimizing Active Processor Time
CoRR
Jessica Chang, Harold N. Gabow, Samir Khuller
2012 A conf
A Model for Minimizing Active Processor Time.
ESA
Jessica Chang, Harold N. Gabow, Samir Khuller
2012 J jnl
A combinatoric interpretation of dual variables for weighted matching and f-factors.
Theor. Comput. Sci.
Harold N. Gabow
2012 J jnl
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings
CoRR
Marek Cygan, Harold N. Gabow, Piotr Sankowski
2012 A* conf
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings.
FOCS
Marek Cygan, Harold N. Gabow, Piotr Sankowski
2012 J jnl
Iterated Rounding Algorithms for the Smallest
SIAM J. Comput.
Harold N. Gabow, Suzanne Gallagher
2009 J jnl
Approximating the smallest
Networks
Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson
2009 J jnl
Foreword to special issue on SODA 2007.
ACM Trans. Algorithms
Harold N. Gabow
2008 B conf
Finding Long Paths, Cycles and Circuits.
ISAAC
Harold N. Gabow, Shuxin Nie
2008 J jnl
Finding a long directed cycle.
ACM Trans. Algorithms
Harold N. Gabow, Shuxin Nie
2008 A* conf
Iterated rounding algorithms for the smallest
SODA
Harold N. Gabow, Suzanne Gallagher
2007 J jnl
Finding Paths and Cycles of Superpolylogarithmic Length.
SIAM J. Comput.
Harold N. Gabow
2007 J jnl
Introduction to SODA 2002 and 2003 special issue.
ACM Trans. Algorithms
Harold N. Gabow, Michael A. Bender, Martin Farach-Colton
2007 J jnl
On the L
Math. Program.
Harold N. Gabow
2006 J jnl
An Algorithm for Strongly Connected Component Analysis in
Formal Methods Syst. Des.
Roderick Bloem, Harold N. Gabow, Fabio Somenzi
2006 A* conf
Upper degree-constrained partial orientations.
SODA
Harold N. Gabow
2006 J jnl
Using expander graphs to find vertex connectivity.
J. ACM
Harold N. Gabow
2005 J jnl
An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph.
SIAM J. Discret. Math.
Harold N. Gabow
2005 A* conf
Approximating the smallest
SODA
Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson
2005 J jnl
Editor's foreword.
ACM Trans. Algorithms
Harold N. Gabow
2005 B conf
On the L
IPCO
Harold N. Gabow
2005 A* ed.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005
STOC
Harold N. Gabow, Ronald Fagin
2004 J jnl
An Ear Decomposition Approach to Approximating the Smallest 3-Edge Connected Spanning Subgraph of a Multigraph.
SIAM J. Discret. Math.
Harold N. Gabow
2004 J jnl
Coloring Algorithms On Subcubic Graphs.
Int. J. Found. Comput. Sci.
San Skulrattanakulchai, Harold N. Gabow
2004 A* conf
Finding a long directed cycle.
SODA
Harold N. Gabow, Shuxin Nie
2004 A* conf
Finding paths and cycles of superpolylogarithmic length.
STOC
Harold N. Gabow
2004 A* conf
Special edges, and approximating the smallest directed
SODA
Harold N. Gabow
2003 A* conf
Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph.
SODA
Harold N. Gabow
2003 — ch.
Graphs in Computer Science.
Handbook of Graph Theory
Harold N. Gabow, Camil Demetrescu, Irene Finocchi, Giuseppe Francesco Italiano, Giuseppe Liotta, Roberto Tamassia, Richard B. Borie, R. Gary Parker, Craig A. Tovey
2003 J jnl
The limits of input-queued switch performance with future packet arrival information.
Comput. Networks
Timothy X. Brown, Harold N. Gabow
2002 A* conf
An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph.
SODA
Harold N. Gabow
2002 Misc conf
Coloring Algorithms on Subcubic Graphs.
COCOON
Harold N. Gabow, San Skulrattanakulchai
2002 — conf
The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms.
SWAT
Harold N. Gabow, Seth Pettie
2001 J jnl
A Network-Flow-Based Scheduler: Design, Performance History, and Experimental Analysis.
ACM J. Exp. Algorithmics
Harold N. Gabow, Tadayoshi Kohno
2001 J jnl
Bipartition constrained edge-splitting in directed graphs.
Discret. Appl. Math.
Harold N. Gabow, Tibor Jordán
2001 B conf
Maximum flow-life curve for a wireless ad hoc network.
MobiHoc
Timothy X. Brown, Harold N. Gabow, Qi Zhang
2001 J jnl
Unique Maximum Matching Algorithms.
J. Algorithms
Harold N. Gabow, Haim Kaplan, Robert Endre Tarjan
2000 B conf
An Algorithm for Strongly Connected Component Analysis in
FMCAD
Roderick Bloem, Harold N. Gabow, Fabio Somenzi
2000 J jnl
Computing Vertex Connectivity: New Bounds from Old Techniques.
J. Algorithms
Monika Rauch Henzinger, Satish Rao, Harold N. Gabow
2000 J jnl
How to Make a Square Grid Framework with Cables Rigid.
SIAM J. Comput.
Harold N. Gabow, Tibor Jordán
2000 J jnl
Incrementing Bipartite Digraph Edge-Connectivity.
J. Comb. Optim.
Harold N. Gabow, Tibor Jordán
2000 J jnl
Parallel tetrahedral mesh adaptation with dynamic load balancing.
Parallel Comput.
Leonid Oliker, Rupak Biswas, Harold N. Gabow
2000 J jnl
Path-based depth-first search for strong and biconnected components.
Inf. Process. Lett.
Harold N. Gabow
2000 J jnl
Protein domain decomposition using a graph-theoretic approach.
Bioinform.
Ying Xu, Dong Xu, Harold N. Gabow
2000 A* conf
Using Expander Graphs to Find Vertex Connectivity.
FOCS
Harold N. Gabow
1999 J jnl
Edge-Connectivity Augmentation with Partition Constraints.
SIAM J. Discret. Math.
Jørgen Bang-Jensen, Harold N. Gabow, Tibor Jordán, Zoltán Szigeti
1999 A* conf
How to Make a Square Grid Framework with Cables Rigid.
SODA
Harold N. Gabow, Tibor Jordán
1999 A* conf
Unique Maximum Matching Algorithms.
STOC
Harold N. Gabow, Haim Kaplan, Robert Endre Tarjan
1998 J jnl
Algorithms for Graphic Polymatroids and Parametris s-Sets.
J. Algorithms
Harold N. Gabow
1998 J jnl
An RNA folding method capable of identifying pseudoknots and base triples.
Bioinform.
Jack E. Tabaska, Robert B. Cary, Harold N. Gabow, Gary D. Stormo
1998 J jnl
An efficient approximation algorithm for the survivable network design problem.
Math. Program.
Harold N. Gabow, Michel X. Goemans, David P. Williamson
1998 A* conf
Edge-Connectivity Augmentation with Partition Constraints.
SODA
Jørgen Bang-Jensen, Harold N. Gabow, Tibor Jordán, Zoltán Szigeti
1998 J jnl
Packing algorithms for arborescences (and spanning trees) in capacitated graphs.
Math. Program.
Harold N. Gabow, K. S. Manu
1998 — conf
Performance Analysis and Portability of the PLUM Load Balancing System.
Euro-Par
Leonid Oliker, Rupak Biswas, Harold N. Gabow
1996 A* conf
Computing Vertex Connectivity: New Bounds from Old Techniques.
FOCS
Monika Rauch Henzinger, Satish Rao, Harold N. Gabow
1996 J jnl
Efficient Theoretic and Practical Algorithms for Linear Matroid Intersection Problems.
J. Comput. Syst. Sci.
Harold N. Gabow, Ying Xu
1996 A* conf
Perfect Arborescence Packing in Preflow Mincut Graphs.
SODA
Harold N. Gabow
1995 J jnl
A Matroid Approach to Finding Edge Connectivity and Packing Arborescences.
J. Comput. Syst. Sci.
Harold N. Gabow
1995 A* conf
Algorithms for Graphic Polymatroids and Parametric s-Sets.
SODA
Harold N. Gabow
1995 J jnl
Centroids, Representations, and Submodular Flows.
J. Algorithms
Harold N. Gabow
1995 B conf
Packing Algorithms for Arborescences (and Spanning Trees) in Capacitated Graphs.
IPCO
Harold N. Gabow, K. S. Manu
1994 J jnl
An O(n²) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs.
J. Algorithms
Andrzej Ehrenfeucht, Harold N. Gabow, Ross M. McConnell, Stephen J. Sullivan
1994 J jnl
Editor's Foreword: Special Issur on Network Flow Algorithms.
Algorithmica
Harold N. Gabow
1994 A* conf
Efficient splitting off algorithms for graphs.
STOC
Harold N. Gabow
1994 B conf
Fast Algorithms for Transversal Matroid Intersection Problems
ISAAC
Ying Xu, Harold N. Gabow
1993 A* conf
A Framework for Cost-scaling Algorithms for Submodular Flow Problems
FOCS
Harold N. Gabow
1993 A* conf
A Representation for Crossing Set Families with Applications to Submodular Flow Problems.
SODA
Harold N. Gabow
1993 B conf
An efficient approximation algorithm for the survivable network design problem.
IPCO
Harold N. Gabow, Michel X. Goemans, David P. Williamson
1992 J jnl
Forests, Frames, and Games: Algorithms for Matroid Sums and Applications.
Algorithmica
Harold N. Gabow, Herbert H. Westermann
1991 A* conf
A Matroid Approach to Finding Edge Connectivity and Packing Arborescences
STOC
Harold N. Gabow
1991 A* conf
Applications of a Poset Representation to Edge Connectivity and Graph Rigidity
FOCS
Harold N. Gabow
1991 J jnl
Faster Scaling Algorithms for General Graph-Matching Problems.
J. ACM
Harold N. Gabow, Robert Endre Tarjan
1990 A* conf
Data Structures for Weighted Matching and Nearest Common Ancestors with Linking.
SODA
Harold N. Gabow
1989 A* conf
Efficient Algorithms for Independent Assignments on Graphic and Linear Matroids
FOCS
Harold N. Gabow, Ying Xu
1989 J jnl
Efficient implementation of graph algorithms using contraction.
J. ACM
Harold N. Gabow, Zvi Galil, Thomas H. Spencer
1989 J jnl
Faster Scaling Algorithms for Network Problems.
SIAM J. Comput.
Harold N. Gabow, Robert Endre Tarjan
1988 J jnl
A Linear-Time Algorithm for Finding a Minimum Spanning Pseudoforest.
Inf. Process. Lett.
Harold N. Gabow, Robert Endre Tarjan
1988 J jnl
Algorithms for Two Bottleneck Optimization Problems.
J. Algorithms
Harold N. Gabow, Robert Endre Tarjan
1988 A* conf
Almost-Optimum Speed-ups of Algorithms for Bipartite Matching and Related Problems
STOC
Harold N. Gabow, Robert Endre Tarjan
1988 A* conf
Forests, Frames and Games: Algorithms for Matroid Sums and Applications
STOC
Harold N. Gabow, Herbert H. Westermann
1988 J jnl
Relaxed Heaps: An Alternative to Fibonacci Heaps with Applications to Parallel Computation.
Commun. ACM
James R. Driscoll, Harold N. Gabow, Ruth Shrairman, Robert Endre Tarjan
1988 J jnl
Scheduling UET Systems on Two Uniform Processors and Length Two Pipelines.
SIAM J. Comput.
Harold N. Gabow
1986 J jnl
An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs.
SIAM J. Comput.
Zvi Galil, Silvio Micali, Harold N. Gabow
1986 J jnl
An augmenting path algorithm for linear matroid parity.
Comb.
Harold N. Gabow, Matthias F. M. Stallmann
1986 J jnl
Efficient algorithms for finding minimum spanning trees in undirected and directed graphs.
Comb.
Harold N. Gabow, Zvi Galil, Thomas H. Spencer, Robert Endre Tarjan
1985 J jnl
A Linear-Time Algorithm for a Special Case of Disjoint Set Union.
J. Comput. Syst. Sci.
Harold N. Gabow, Robert Endre Tarjan
1985 A* conf
A Scaling Algorithm for Weighted Matching on General Graphs
FOCS
Harold N. Gabow
1985 A* conf
Efficient Algorithms for Graphic Matroid Intersection and Parity (Extended Abstract).
ICALP
Harold N. Gabow, Matthias F. M. Stallmann
1985 J jnl
Scaling Algorithms for Network Problems.
J. Comput. Syst. Sci.
Harold N. Gabow
1984 A* conf
An Augmenting Path Algorithm for the Parity Problem on Linear Matroids
FOCS
Matthias F. M. Stallmann, Harold N. Gabow
1984 J jnl
Efficient Algorithms for a Family of Matroid Intersection Problems.
J. Algorithms
Harold N. Gabow, Robert Endre Tarjan
1984 A* conf
Efficient Implementation of Graph Algorithms Using Contraction
FOCS
Harold N. Gabow, Zvi Galil, Thomas H. Spencer
1984 A* conf
Scaling and Related Techniques for Geometry Problems
STOC
Harold N. Gabow, Jon Louis Bentley, Robert Endre Tarjan
1983 A* conf
A Linear-Time Algorithm for a Special Case of Disjoint Set Union
STOC
Harold N. Gabow, Robert Endre Tarjan
1983 A* conf
An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems
STOC
Harold N. Gabow
1983 A* conf
Scaling Algorithms for Network Problems
FOCS
Harold N. Gabow
1982 J jnl
Algorithms for Edge Coloring Bipartite Graphs and Multigraphs.
SIAM J. Comput.
Harold N. Gabow, Oded Kariv
1982 J jnl
An Almost-Linear Algorithm for Two-Processor Scheduling.
J. ACM
Harold N. Gabow
1982 A* conf
Priority Queues with Variable Priority and an O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs
FOCS
Zvi Galil, Silvio Micali, Harold N. Gabow
1981 J jnl
A Linear-Time Recognition Algorithm for Interval Dags.
Inf. Process. Lett.
Harold N. Gabow
1979 J jnl
A Counting Approach to Lower Bounds for Selection Problems.
J. ACM
Frank Fussenegger, Harold N. Gabow
1979 J jnl
Algorithmic proofs of two relations between connectivity and the 1-factors of a graph.
Discret. Math.
Harold N. Gabow
1979 A* conf
Efficient Algorithms for Simple Matroid Intersection Problems
FOCS
Harold N. Gabow, Robert Endre Tarjan
1978 J jnl
A good algorithm for smallest spanning trees with a degree constraint.
Networks
Harold N. Gabow
1978 A* conf
Algorithms for Edge Coloring Bipartite Graphs
STOC
Harold N. Gabow, Oded Kariv
1978 J jnl
Finding All Spanning Trees of Directed and Undirected Graphs.
SIAM J. Comput.
Harold N. Gabow, Eugene W. Myers
1977 J jnl
Two Algorithms for Generating Weighted Spanning Trees in Order.
SIAM J. Comput.
Harold N. Gabow
1976 J jnl
A Note on Degree-Constrained Star Subgraphs of Bipartite Graphs.
Inf. Process. Lett.
Harold N. Gabow
1976 J jnl
An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs.
J. ACM
Harold N. Gabow
1976 J jnl
Decomposing symmetric exchanges in matroid bases.
Math. Program.
Harold N. Gabow
1976 J jnl
On Two Problems in the Generation of Program Test Paths.
IEEE Trans. Software Eng.
Harold N. Gabow, Shachindra N. Maheswari, Leon J. Osterweil
1976 J jnl
Some Improved Bounds on the Number of 1-Factors of n-Connected Graphs.
Inf. Process. Lett.
Harold N. Gabow
1976 A* conf
Using Comparison Trees to Derive Lower Bounds for Selection Problems
FOCS
Frank Fussenegger, Harold N. Gabow
1976 J jnl
Using euler partitions to edge color bipartite multigraphs.
Int. J. Parallel Program.
Harold N. Gabow
1975 J jnl
How to gracefully number certain symmetric trees.
SIGACT News
Harold N. Gabow
1973 — —
Implementation of algorithms for maximum matching on nonbipartite graphs.
Harold N. Gabow