11 citations · 31 across the 8 of their papers we have counts for
9 papers
Blocking Trails for -factors of Multigraphs
Harold N. Gabow
Blocking flows, introduced by Dinic [2] for network flow, have been used to speed up many augmenting-path type algorithms, especially matching algorithms e.g., [18, 23, 16]. We pre…
A Weight-scaling Algorithm for -factors of Multigraphs
Harold Gabow
We discuss combinatorial algorithms for finding a maximum weight -factor on an arbitrary multigraph, for given integral weights of magnitude at most . For simple bipartite gr…
The Weighted Matching Approach to Maximum Cardinality Matching
Harold N. Gabow
Several papers have achieved time for cardinality matching, starting from first principles. This results in a long derivation. We simplify the task by employing well…
Data Structures for Weighted Matching and Extensions to -matching and -factors
Harold N. Gabow
This paper shows the weighted matching problem on general graphs can be solved in time for and the number of vertices and edges, respectively. This was…
A Data Structure for Nearest Common Ancestors with Linking
Harold N. Gabow
Consider a forest that evolves via operations that make the root of one tree the child of a node in another tree. Intermixed with operations are operations, whi…
Set-merging for the Matching Algorithm of Micali and Vazirani
Harold N. Gabow
The algorithm of Micali and Vazirani \cite{MV} finds a maximum cardinality matching in time if an efficient set-merging algorithm is used. The latter is provided by…
Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors
Harold N. Gabow, Piotr Sankowski
Let G=(V,E) be a graph with f:V\to Z_+ a function assigning degree bounds to vertices. We present the first efficient algebraic algorithm to find an f-factor. The time is \tilde{O}…
A Model for Minimizing Active Processor Time
Jessica Chang, Harold N. Gabow, Samir Khuller
We introduce the following elementary scheduling problem. We are given a collection of n jobs, where each job has an integer length as well as a set Ti of time intervals in which i…
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings
Marek Cygan, Harold N. Gabow, Piotr Sankowski
Consider a directed or an undirected graph with integral edge weights from the set [-W, W], that does not contain negative weight cycles. In this paper, we introduce a general fram…