Abstract. A well-known problem m scheduling theory is to execute n umt-lengthjobs subject to precedence constraints on two processors m mmunum fimsh time Previous algorithms begin by finding the...
A Network-Flow-Based Scheduler: Design, Performance History and Experimental Analysis (2007)
Harold N. Gabow, Tadayoshi Kohno
uses network ow techniques to prune an exponentially sized search space. We describe the program design, its performance history at the hospital, and experiments on a simplied version of the program.
Abstract Parallel Tetrahedral Mesh Adaptation with Dynamic Load Balancing 1 (2007)
Leonid Oliker, Rupak Biswas, Harold N. Gabow
The ability to dynamically adapt an unstructured grid is a powerful tool for efciently solving computational problems with evolving physical features. In this paper, we report on our experience...
We present ecient algorithms for three coloring problems on subcubic graphs. (A subcubic graph has maximum degree at most three.) The rst algorithm is for 4-edge coloring, or more generally,...
Harold N. Gabow, Robert E. Tarjan, Haim Kaplan, Haim Kaplan
We consider the problem of testing the uniqueness of maximum matchings, both in the unweighted and in the weighted case. For the unweighted case, we have two results. First, given a graph with n...
Faster Scaling Algorithms for Network Problems, (2005)
Gabow, Harold N., Tarjan, Robert E.
This paper presents algorithms for the assignment problem, the transportation problem and the minimum cost flow problem of operations research. The algorithms finds a minimum cost solution, but run...
Cooperative asynchronous update of shared memory (2005)
Chlebus, Bogdan S., Kowalski, Dariusz, Gabow, Harold N., Fagin, Ronald
The dynamic vertex minimum problem (DVMP) is to maintain the minimum cost edge in a graph that is subject to vertex additions and deletions. DVMP abstracts the clustering operation that is used in...
Abstract. The dynamic vertex minimum problem (DVMP) is to maintain the minimum cost edge in a graph that is subject to vertex additions and deletions. DVMP abstracts the clustering operation that is...
The dynamic vertex minimum problem (DVMP) is to maintain the minimum cost edge in a graph that is subject to vertex additions and deletions. DVMP abstracts the clustering operation that is used in...
Coloring algorithms on subcubic graphs (2002)
Harold N. Gabow, San Skulrattanakulchai
Abstract. We present ecient algorithms for three coloring problems on subcubic graphs (ones with maximum degree 3). These algorithms are based on a simple decomposition principle for subcubic graphs....
Path-based depth-first search for strong and biconnected components (2000)
Key words: Graph, depth-first search, strongly connected component, biconnected component, stack.
Using expander graphs to find vertex connectivity (2000)
Abstract The (vertex) connectivity ^ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known algorithm for finding ^. For a...
An Algorithm for Strongly Connected Component Analysis in n log n Symbolic Steps (2000)
Roderick Bloem, Harold N. Gabow, Fabio Somenzi
We present a symbolic algorithm for strongly connected component decomposition. The algorithm performs O(n log n) image and preimage computations in the worst case, where n is the number of nodes in...
Edge-connectivity augmentation with partition constraints (1999)
When k is even the min-max formula for the partition-constrained problem is a natural generalization of [3]. However this generalization fails when k is odd. We show that at most one more edge is...
Parallel Tetrahedral Mesh Adaptation with Dynamic Load Balancing (1999)
Leonid Oliker, Rupak Biswas, Harold N. Gabow
The ability to dynamically adapt an unstructured grid is a powerful tool for efficiently solving computational problems with evolving physical features. In this paper, we report on our experience...
A Linear-Time Algorithm for Finding a Minimum Spanning Pseudoforest, (1998)
Gabow, Harold N., Tarjan, Robert E.
A pseudoforest is a graph each of whose connected components is a tree or a tree plus an edge; a spanning pseudoforest of a graph contains the greatest number of edges possible. This paper shows that...
Relaxed Heaps: An Alternative to Fibonacci Heaps, (1998)
Driscoll, James R., Gabow, Harold N., Shrairman, Ruth, Tarjan, Robert E.
The relaxed heap is a priority queue data structure that achieves the same amortized time bounds as the Fibonacci heap - a sequence of m decrease key and n delete min operations takes time O(m + n...
Almost-Optimum Parallel Speed-Ups of Algorithms for Bipartite Matching and Related Problems, (1998)
Gabow, Harold N., Tarjan, Robert E.
This paper focuses on algorithms for matching problems that run on an EREW PRAM with p processors. Given is a bipartite graph with n vertices, m edges, and integral edge costs at most N in magnitude....
Faster Scaling Algorithms for General Graph Matching Problems, (1998)
Gabow, Harold N., Tarjan, Robert E.
This paper presents an algorithm for minimum cost matching on a general graph with integral edge costs, that runs in time close to the best known bound for cardinality matching. Specifically, let n,...
Performance Analysis and Portability of the PLUM Load Balancing System (1998)
Leonid Oliker Rupak, Rupak Biswas, Harold N. Gabow
. The ability to dynamically adapt an unstructured mesh is a powerful tool for solving computational problems with evolving physical features; however, an efficient parallel implementation is rather...
Edge-Connectivity Augmentation With Partition Constraints (1997)
Jørgen Bang-Jensen, Harold N. Gabow, Tibor Jordán, Zoltán Szigeti
In the well-solved edge-connectivity augmentation problem we must find a minimum cardinality set F of edges to add to a given undirected graph to make it k-edge-connected. This paper solves the...
Computing vertex connectivity: New bounds from old techniques (1996)
Henzinger, Monika R., Rao, Satish, Gabow, Harold N.
The vertex connectivity K of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the...
Monika R. Henzinger, Satish Rao, Harold N. Gabow
The vertex connectivity � of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the...
An Efficient Approximation Algorithm for the Survivable Network Design Problem (1993)
Abstract The survivable network design problem is to construct a minimum-cost subgraph satisfying certain given edge-connectivity requirements. The first polynomial-time approximation algorithm was...
An Efficient Approximation Algorithm for the Survivable Network Design Problem (1993)
Harold N. Gabow, Michel X. Goemans, David P. Williamson
The survivable network design problem is to construct a minimum-cost subgraph satisfying certain given edge-connectivity requirements. The first polynomial-time approximation algorithm was given by...