Harold N. Gabow

Algorithmica, October, 2023

Blocking Trails for f-factors of Multigraphs.

[BibT_eX]

[DOI]

Algorithmica, October, 2023

Maximum Cardinality f-Matching in Time O(n2/3m).

[BibT_eX]

[DOI]

CoRR, 2023

2021

Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

2018

Data Structures for Weighted Matching and Extensions to b-matching and f-factors.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

2017

A Data Structure for Nearest Common Ancestors with Linking.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

The Weighted Matching Approach to Maximum Cardinality Matching.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2017

2016

The Minset-Poset Approach to Representations of Graph Connectivity.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Data Structures for Weighted Matching and Extensions to $b$-matching and $f$-factors.

[BibT_eX]

[DOI]

CoRR, 2016

2015

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter, and Matchings.

[BibT_eX]

[DOI]

Marek Cygan

J. ACM, 2015

Set-merging for the Matching Algorithm of Micali and Vazirani.

[BibT_eX]

[DOI]

CoRR, 2015

2014

A Model for Minimizing Active Processor Time.

[BibT_eX]

[DOI]

Jessica Chang

Samir Khuller

Algorithmica, 2014

2013

Algebraic Algorithms for B-Matching, Shortest Undirected Paths, and F-Factors.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

A combinatoric interpretation of dual variables for weighted matching and f-factors.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph.

[BibT_eX]

[DOI]

Suzanne Gallagher

SIAM J. Comput., 2012

2009

Foreword to special issue on SODA 2007.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

Approximating the smallest k-edge connected spanning subgraph by LP-rounding.

[BibT_eX]

[DOI]

Networks, 2009

2008

Finding a long directed cycle.

[BibT_eX]

[DOI]

Shuxin Nie

ACM Trans. Algorithms, 2008

Finding Long Paths, Cycles and Circuits.

[BibT_eX]

[DOI]

Shuxin Nie

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

2007

Introduction to SODA 2002 and 2003 special issue.

[BibT_eX]

[DOI]

Michael A. Bender

Martin Farach-Colton

ACM Trans. Algorithms, 2007

Finding Paths and Cycles of Superpolylogarithmic Length.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

On the Linfinity-norm of extreme points for crossing supermodular directed network LPs.

[BibT_eX]

[DOI]

Math. Program., 2007

2006

Using expander graphs to find vertex connectivity.

[BibT_eX]

[DOI]

J. ACM, 2006

An Algorithm for Strongly Connected Component Analysis in n log n Symbolic Steps.

[BibT_eX]

[DOI]

Roderick Bloem

Fabio Somenzi

Formal Methods Syst. Des., 2006

Upper degree-constrained partial orientations.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005

Editor's foreword.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2005

An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2005

2004

An Ear Decomposition Approach to Approximating the Smallest 3-Edge Connected Spanning Subgraph of a Multigraph.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2004

Coloring Algorithms On Subcubic Graphs.

[BibT_eX]

[DOI]

San Skulrattanakulchai

Int. J. Found. Comput. Sci., 2004

Special edges, and approximating the smallest directed k-edge connected spanning subgraph.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003

The limits of input-queued switch performance with future packet arrival information.

[BibT_eX]

[DOI]

Timothy X. Brown

Comput. Networks, 2003

Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Graphs in Computer Science.

[BibT_eX]

[DOI]

Giuseppe Francesco Italiano

Camil Demetrescu

Irene Finocchi

Proceedings of the Handbook of Graph Theory., 2003

2002

The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms.

[BibT_eX]

[DOI]

Seth Pettie

Proceedings of the Algorithm Theory, 2002

2001

A Network-Flow-Based Scheduler: Design, Performance History, and Experimental Analysis.

[BibT_eX]

[DOI]

Tadayoshi Kohno

ACM J. Exp. Algorithmics, 2001

Unique Maximum Matching Algorithms.

[BibT_eX]

[DOI]

Haim Kaplan

J. Algorithms, 2001

Bipartition constrained edge-splitting in directed graphs.

[BibT_eX]

[DOI]

Tibor Jordán

Discret. Appl. Math., 2001

Maximum flow-life curve for a wireless ad hoc network.

[BibT_eX]

[DOI]

Timothy X. Brown

Qi Zhang

Proceedings of the 2nd ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, 2001

2000

How to Make a Square Grid Framework with Cables Rigid.

[BibT_eX]

[DOI]

Tibor Jordán

SIAM J. Comput., 2000

Parallel tetrahedral mesh adaptation with dynamic load balancing.

[BibT_eX]

[DOI]

Leonid Oliker

Rupak Biswas

Parallel Comput., 2000

Incrementing Bipartite Digraph Edge-Connectivity.

[BibT_eX]

[DOI]

Tibor Jordán

J. Comb. Optim., 2000

Computing Vertex Connectivity: New Bounds from Old Techniques.

[BibT_eX]

[DOI]

Monika Rauch Henzinger

Satish Rao

J. Algorithms, 2000

Path-based depth-first search for strong and biconnected components.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

Protein domain decomposition using a graph-theoretic approach.

[BibT_eX]

[DOI]

Dong Xu

Bioinform., 2000

1999

Edge-Connectivity Augmentation with Partition Constraints.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1999

1998

Packing algorithms for arborescences (and spanning trees) in capacitated graphs.

[BibT_eX]

[DOI]

K. S. Manu

Math. Program., 1998

An efficient approximation algorithm for the survivable network design problem.

[BibT_eX]

[DOI]

Michel X. Goemans

David P. Williamson

Math. Program., 1998

Algorithms for Graphic Polymatroids and Parametris s-Sets.

[BibT_eX]

[DOI]

J. Algorithms, 1998

An RNA folding method capable of identifying pseudoknots and base triples.

[BibT_eX]

[DOI]

Bioinform., 1998

Performance Analysis and Portability of the PLUM Load Balancing System.

[BibT_eX]

[DOI]

Leonid Oliker

Rupak Biswas

Proceedings of the Euro-Par '98 Parallel Processing, 1998

1996

Efficient Theoretic and Practical Algorithms for Linear Matroid Intersection Problems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

Perfect Arborescence Packing in Preflow Mincut Graphs.

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

1995

A Matroid Approach to Finding Edge Connectivity and Packing Arborescences.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1995

Centroids, Representations, and Submodular Flows.

[BibT_eX]

[DOI]

J. Algorithms, 1995

Algorithms for Graphic Polymatroids and Parametric s-Sets.

[BibT_eX]

[DOI]

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

1994

An O(n²) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs.

[BibT_eX]

[DOI]

J. Algorithms, 1994

Editor's Foreword: Special Issur on Network Flow Algorithms.

[BibT_eX]

[DOI]

Algorithmica, 1994

Efficient splitting off algorithms for graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Fast Algorithms for Transversal Matroid Intersection Problems

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

1993

A Representation for Crossing Set Families with Applications to Submodular Flow Problems.

[BibT_eX]

[DOI]

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

A Framework for Cost-scaling Algorithms for Submodular Flow Problems

[BibT_eX]

[DOI]

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

Forests, Frames, and Games: Algorithms for Matroid Sums and Applications.

[BibT_eX]

[DOI]

Herbert H. Westermann

Algorithmica, 1992

1991

Faster Scaling Algorithms for General Graph-Matching Problems.

[BibT_eX]

[DOI]

J. ACM, 1991

Applications of a Poset Representation to Edge Connectivity and Graph Rigidity

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

Data Structures for Weighted Matching and Nearest Common Ancestors with Linking.

[BibT_eX]

[DOI]

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

1989

Faster Scaling Algorithms for Network Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

Efficient implementation of graph algorithms using contraction.

[BibT_eX]

[DOI]

Zvi Galil

Thomas H. Spencer

J. ACM, 1989

Efficient Algorithms for Independent Assignments on Graphic and Linear Matroids

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

Algorithms for Two Bottleneck Optimization Problems.

[BibT_eX]

[DOI]

J. Algorithms, 1988

A Linear-Time Algorithm for Finding a Minimum Spanning Pseudoforest.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1988

Relaxed Heaps: An Alternative to Fibonacci Heaps with Applications to Parallel Computation.

[BibT_eX]

[DOI]

Commun. ACM, 1988

Almost-Optimum Speed-ups of Algorithms for Bipartite Matching and Related Problems

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Zvi Galil

Silvio Micali

SIAM J. Comput., 1986

An augmenting path algorithm for linear matroid parity.

[BibT_eX]

[DOI]

Matthias F. M. Stallmann

Comb., 1986

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs.

[BibT_eX]

[DOI]

Comb., 1986

1985

A Linear-Time Algorithm for a Special Case of Disjoint Set Union.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1985

Scaling Algorithms for Network Problems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1985

Efficient Algorithms for Graphic Matroid Intersection and Parity (Extended Abstract).

[BibT_eX]

[DOI]

Matthias F. M. Stallmann

Proceedings of the Automata, 1985

A Scaling Algorithm for Weighted Matching on General Graphs

[BibT_eX]

[DOI]

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984

Efficient Algorithms for a Family of Matroid Intersection Problems.

[BibT_eX]

[DOI]

J. Algorithms, 1984

Scaling and Related Techniques for Geometry Problems

[BibT_eX]

[DOI]

Jon Louis Bentley

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

[BibT_eX]

[DOI]

Matthias F. M. Stallmann

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems

[BibT_eX]

[DOI]

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982

Algorithms for Edge Coloring Bipartite Graphs and Multigraphs.

[BibT_eX]

[DOI]

Oded Kariv

SIAM J. Comput., 1982

An Almost-Linear Algorithm for Two-Processor Scheduling.

[BibT_eX]

[DOI]

J. ACM, 1982

Priority Queues with Variable Priority and an O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs

[BibT_eX]

[DOI]

Zvi Galil

Silvio Micali

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981

A Linear-Time Recognition Algorithm for Interval Dags.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1981

1979

A Counting Approach to Lower Bounds for Selection Problems.

[BibT_eX]

[DOI]

Frank Fussenegger

J. ACM, 1979

Algorithmic proofs of two relations between connectivity and the 1-factors of a graph.

[BibT_eX]

[DOI]

Discret. Math., 1979

Efficient Algorithms for Simple Matroid Intersection Problems

[BibT_eX]

[DOI]

Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978

Finding All Spanning Trees of Directed and Undirected Graphs.

[BibT_eX]

[DOI]

Eugene W. Myers

SIAM J. Comput., 1978

A good algorithm for smallest spanning trees with a degree constraint.

[BibT_eX]

[DOI]

Networks, 1978

Algorithms for Edge Coloring Bipartite Graphs

[BibT_eX]

[DOI]

Oded Kariv

Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978

1977

Two Algorithms for Generating Weighted Spanning Trees in Order.

[BibT_eX]

[DOI]

SIAM J. Comput., 1977

1976

On Two Problems in the Generation of Program Test Paths.

[BibT_eX]

[DOI]

Shachindra N. Maheswari

Leon J. Osterweil

IEEE Trans. Software Eng., 1976

Decomposing symmetric exchanges in matroid bases.

[BibT_eX]

[DOI]

Math. Program., 1976

An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs.

[BibT_eX]

[DOI]

J. ACM, 1976

A Note on Degree-Constrained Star Subgraphs of Bipartite Graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1976

Some Improved Bounds on the Number of 1-Factors of n-Connected Graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1976

Using euler partitions to edge color bipartite multigraphs.

[BibT_eX]

[DOI]

Int. J. Parallel Program., 1976

Using Comparison Trees to Derive Lower Bounds for Selection Problems

[BibT_eX]

[DOI]

Frank Fussenegger

Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976

1975

How to gracefully number certain symmetric trees.

[BibT_eX]

[DOI]

SIGACT News, 1975

1973

Implementation of algorithms for maximum matching on nonbipartite graphs.

[BibT_eX]

[DOI]