Harold N. Gabow
According to our database^{1},
Harold N. Gabow
authored at least 103 papers
between 1976 and 2018.
Collaborative distances:
Collaborative distances:
Awards
ACM Fellow
ACM Fellow 2002, "For contributions to efficient algorithms to flows, connectivity and matching.".
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at dl.acm.org
On csauthors.net:
Bibliography
2018
Data Structures for Weighted Matching and Extensions to bmatching and ffactors.
ACM Trans. Algorithms, 2018
2017
A Data Structure for Nearest Common Ancestors with Linking.
ACM Trans. Algorithms, 2017
The Weighted Matching Approach to Maximum Cardinality Matching.
Fundam. Inform., 2017
2016
The MinsetPoset Approach to Representations of Graph Connectivity.
ACM Trans. Algorithms, 2016
2015
Algorithmic Applications of BaurStrassen's Theorem: Shortest Cycles, Diameter, and Matchings.
J. ACM, 2015
2013
Algebraic Algorithms for BMatching, Shortest Undirected Paths, and FFactors.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013
2012
A combinatoric interpretation of dual variables for weighted matching and ffactors.
Theor. Comput. Sci., 2012
Algorithmic Applications of BaurStrassen's Theorem: Shortest Cycles, Diameter and Matchings.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012
A Model for Minimizing Active Processor Time.
Proceedings of the Algorithms  ESA 2012, 2012
2009
Foreword to special issue on SODA 2007.
ACM Trans. Algorithms, 2009
2008
Iterated rounding algorithms for the smallest kedge connected spanning subgraph.
Proceedings of the Nineteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2008
Finding Long Paths, Cycles and Circuits.
Proceedings of the Algorithms and Computation, 19th International Symposium, 2008
2007
Introduction to SODA 2002 and 2003 special issue.
ACM Trans. Algorithms, 2007
2006
Upper degreeconstrained partial orientations.
Proceedings of the Seventeenth Annual ACMSIAM Symposium on Discrete Algorithms, 2006
2005
Editor's foreword.
ACM Trans. Algorithms, 2005
An Improved Analysis for Approximating the Smallest kEdge Connected Spanning Subgraph of a Multigraph.
SIAM J. Discrete Math., 2005
Approximating the smallest kedge connected spanning subgraph by LProunding.
Proceedings of the Sixteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2005
On the L_{infinity}Norm of Extreme Points for Crossing Supermodular Directed Network LPs.
Proceedings of the Integer Programming and Combinatorial Optimization, 2005
2004
Coloring Algorithms On Subcubic Graphs.
Int. J. Found. Comput. Sci., 2004
Finding paths and cycles of superpolylogarithmic length.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004
Finding a long directed cycle.
Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2004
Special edges, and approximating the smallest directed kedge connected spanning subgraph.
Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2004
2003
The limits of inputqueued switch performance with future packet arrival information.
Computer Networks, 2003
Better performance bounds for finding the smallest kedge connected spanning subgraph of a multigraph.
Proceedings of the Fourteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2003
Graphs in Computer Science.
Proceedings of the Handbook of Graph Theory., 2003
2002
The Dynamic Vertex Minimum Problem and Its Application to ClusteringType Approximation Algorithms.
Proceedings of the Algorithm Theory, 2002
An ear decomposition approach to approximating the smallest 3edge connected spanning subgraph of a multigraph.
Proceedings of the Thirteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2002
Coloring Algorithms on Subcubic Graphs.
Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002
2001
A NetworkFlowBased Scheduler: Design, Performance History, and Experimental Analysis.
ACM Journal of Experimental Algorithmics, 2001
Bipartition constrained edgesplitting in directed graphs.
Discrete Applied Mathematics, 2001
Maximum flowlife curve for a wireless ad hoc network.
Proceedings of the 2nd ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, 2001
2000
Parallel tetrahedral mesh adaptation with dynamic load balancing.
Parallel Computing, 2000
Incrementing Bipartite Digraph EdgeConnectivity.
J. Comb. Optim., 2000
Pathbased depthfirst search for strong and biconnected components.
Inf. Process. Lett., 2000
Protein domain decomposition using a graphtheoretic approach.
Bioinformatics, 2000
Using Expander Graphs to Find Vertex Connectivity.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000
An Algorithm for Strongly Connected Component Analysis in n log n Symbolic Steps.
Proceedings of the Formal Methods in ComputerAided Design, Third International Conference, 2000
1999
Unique Maximum Matching Algorithms.
Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, 1999
How to Make a Square Grid Framework with Cables Rigid.
Proceedings of the Tenth Annual ACMSIAM Symposium on Discrete Algorithms, 1999
1998
Algorithms for Graphic Polymatroids and Parametris sSets.
J. Algorithms, 1998
An RNA folding method capable of identifying pseudoknots and base triples.
Bioinformatics, 1998
EdgeConnectivity Augmentation with Partition Constraints.
Proceedings of the Ninth Annual ACMSIAM Symposium on Discrete Algorithms, 1998
Performance Analysis and Portability of the PLUM Load Balancing System.
Proceedings of the EuroPar '98 Parallel Processing, 1998
1996
Efficient Theoretic and Practical Algorithms for Linear Matroid Intersection Problems.
J. Comput. Syst. Sci., 1996
Perfect Arborescence Packing in Preflow Mincut Graphs.
Proceedings of the Seventh Annual ACMSIAM Symposium on Discrete Algorithms, 1996
Computing Vertex Connectivity: New Bounds from Old Techniques.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
1995
A Matroid Approach to Finding Edge Connectivity and Packing Arborescences.
J. Comput. Syst. Sci., 1995
Centroids, Representations, and Submodular Flows.
J. Algorithms, 1995
Algorithms for Graphic Polymatroids and Parametric sSets.
Proceedings of the Sixth Annual ACMSIAM Symposium on Discrete Algorithms, 1995
Packing Algorithms for Arborescences (and Spanning Trees) in Capacitated Graphs.
Proceedings of the Integer Programming and Combinatorial Optimization, 1995
1994
An O(n²) DivideandConquer Algorithm for the Prime Tree Decomposition of TwoStructures and Modular Decomposition of Graphs.
J. Algorithms, 1994
Editor's Foreword: Special Issur on Network Flow Algorithms.
Algorithmica, 1994
Efficient splitting off algorithms for graphs.
Proceedings of the TwentySixth Annual ACM Symposium on Theory of Computing, 1994
Fast Algorithms for Transversal Matroid Intersection Problems
Proceedings of the Algorithms and Computation, 5th International Symposium, 1994
1993
A Representation for Crossing Set Families with Applications to Submodular Flow Problems.
Proceedings of the Fourth Annual ACM/SIGACTSIAM Symposium on Discrete Algorithms, 1993
An efficient approximation algorithm for the survivable network design problem.
Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993
A Framework for Costscaling Algorithms for Submodular Flow Problems
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993
1992
Forests, Frames, and Games: Algorithms for Matroid Sums and Applications.
Algorithmica, 1992
1991
Faster Scaling Algorithms for General GraphMatching Problems.
J. ACM, 1991
A Matroid Approach to Finding Edge Connectivity and Packing Arborescences
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991
Applications of a Poset Representation to Edge Connectivity and Graph Rigidity
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991
1990
Data Structures for Weighted Matching and Nearest Common Ancestors with Linking.
Proceedings of the First Annual ACMSIAM Symposium on Discrete Algorithms, 1990
1989
Faster Scaling Algorithms for Network Problems.
SIAM J. Comput., 1989
Efficient implementation of graph algorithms using contraction.
J. ACM, 1989
Efficient Algorithms for Independent Assignments on Graphic and Linear Matroids
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989
1988
Scheduling UET Systems on Two Uniform Processors and Length Two Pipelines.
SIAM J. Comput., 1988
Algorithms for Two Bottleneck Optimization Problems.
J. Algorithms, 1988
A LinearTime Algorithm for Finding a Minimum Spanning Pseudoforest.
Inf. Process. Lett., 1988
Relaxed Heaps: An Alternative to Fibonacci Heaps with Applications to Parallel Computation.
Commun. ACM, 1988
Forests, Frames and Games: Algorithms for Matroid Sums and Applications
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988
AlmostOptimum Speedups of Algorithms for Bipartite Matching and Related Problems
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988
1986
An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs.
SIAM J. Comput., 1986
An augmenting path algorithm for linear matroid parity.
Combinatorica, 1986
Efficient algorithms for finding minimum spanning trees in undirected and directed graphs.
Combinatorica, 1986
1985
A LinearTime Algorithm for a Special Case of Disjoint Set Union.
J. Comput. Syst. Sci., 1985
Scaling Algorithms for Network Problems.
J. Comput. Syst. Sci., 1985
Efficient Algorithms for Graphic Matroid Intersection and Parity (Extended Abstract).
Proceedings of the Automata, 1985
A Scaling Algorithm for Weighted Matching on General Graphs
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
1984
Efficient Algorithms for a Family of Matroid Intersection Problems.
J. Algorithms, 1984
Scaling and Related Techniques for Geometry Problems
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984
An Augmenting Path Algorithm for the Parity Problem on Linear Matroids
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984
Efficient Implementation of Graph Algorithms Using Contraction
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984
1983
A LinearTime Algorithm for a Special Case of Disjoint Set Union
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983
An Efficient Reduction Technique for DegreeConstrained Subgraph and Bidirected Network Flow Problems
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983
Scaling Algorithms for Network Problems
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983
1982
Algorithms for Edge Coloring Bipartite Graphs and Multigraphs.
SIAM J. Comput., 1982
An AlmostLinear Algorithm for TwoProcessor Scheduling.
J. ACM, 1982
Priority Queues with Variable Priority and an O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982
1981
A LinearTime Recognition Algorithm for Interval Dags.
Inf. Process. Lett., 1981
1979
A Counting Approach to Lower Bounds for Selection Problems.
J. ACM, 1979
Algorithmic proofs of two relations between connectivity and the 1factors of a graph.
Discrete Mathematics, 1979
Efficient Algorithms for Simple Matroid Intersection Problems
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979
1978
Finding All Spanning Trees of Directed and Undirected Graphs.
SIAM J. Comput., 1978
A good algorithm for smallest spanning trees with a degree constraint.
Networks, 1978
Algorithms for Edge Coloring Bipartite Graphs
Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978
1977
Two Algorithms for Generating Weighted Spanning Trees in Order.
SIAM J. Comput., 1977
1976
On Two Problems in the Generation of Program Test Paths.
IEEE Trans. Software Eng., 1976
Decomposing symmetric exchanges in matroid bases.
Math. Program., 1976
An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs.
J. ACM, 1976
A Note on DegreeConstrained Star Subgraphs of Bipartite Graphs.
Inf. Process. Lett., 1976
Some Improved Bounds on the Number of 1Factors of nConnected Graphs.
Inf. Process. Lett., 1976
Using euler partitions to edge color bipartite multigraphs.
International Journal of Parallel Programming, 1976
Using Comparison Trees to Derive Lower Bounds for Selection Problems
Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976