Joseph Cheriyan

Kevin K. H. Cheung

Oper. Res. Lett., July, 2023

On a partition LP relaxation for min-cost 2-node connected spanning subgraphs.

[BibT_eX]

[DOI]

Logan Grout

Bundit Laekhanukit

Oper. Res. Lett., May, 2023

Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Algorithms for 2-Connected Network Design and Flexible Steiner Trees with a Constant Number of Terminals.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., September, 2022

Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs.

[BibT_eX]

[DOI]

Discret. Math., 2022

Extensions of the (p, q)-Flexible-Graph-Connectivity model.

[BibT_eX]

[DOI]

CoRR, 2022

Approximating (p, 2) flexible graph connectivity via the primal-dual method.

[BibT_eX]

[DOI]

CoRR, 2022

2021

A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs.

[BibT_eX]

[DOI]

R. Ravi

Martin Skutella

Oper. Res. Lett., 2021

A 2-Approximation Algorithm for Flexible Graph Connectivity.

[BibT_eX]

[DOI]

CoRR, 2021

An Improved Approximation Algorithm for the Matching Augmentation Problem.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

Approximation Algorithms for Flexible Graph Connectivity.

[BibT_eX]

[DOI]

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

2020

The matching augmentation problem: a $\frac{7}{4}$-approximation algorithm.

[BibT_eX]

[DOI]

Math. Program., 2020

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2020

2018

On Eulerian orientations of even-degree hypercubes.

[BibT_eX]

[DOI]

Maxwell Levit

L. Sunil Chandran

Oper. Res. Lett., 2018

The Matching Augmentation Problem: A 7/4-Approximation Algorithm.

[BibT_eX]

[DOI]

CoRR, 2018

Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II.

[BibT_eX]

[DOI]

Algorithmica, 2018

Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP.

[BibT_eX]

[DOI]

Algorithmica, 2018

2016

Approximating (Unweighted) Tree Augmentation via Lift-and-Project (Part 0: $1.8+ε$ approximation for (Unweighted) TAP).

[BibT_eX]

[DOI]

CoRR, 2016

2014

Packing of rigid spanning subgraphs and spanning trees.

[BibT_eX]

[DOI]

Olivier Durand de Gevigney

Zoltán Szigeti

J. Comb. Theory B, 2014

2013

Approximation Algorithms for Minimum-Cost $k\hbox{-}(S, T)$ Connected Digraphs.

[BibT_eX]

[DOI]

Bundit Laekhanukit

SIAM J. Discret. Math., 2013

A bad example for the iterative rounding method for mincost k-connected spanning subgraphs.

[BibT_eX]

[DOI]

Ashkan Aazami

Bundit Laekhanukit

Discret. Optim., 2013

On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy.

[BibT_eX]

[DOI]

Konstantinos Georgiou

Sahil Singla

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs.

[BibT_eX]

[DOI]

László A. Végh

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

2012

On orienting graphs for connectivity: Projective planes and Halin graphs.

[BibT_eX]

[DOI]

Chenglong Zou

Oper. Res. Lett., 2012

On the maximum size of a minimal k-edge connected augmentation.

[BibT_eX]

[DOI]

Andrei V. Kotlov

J. Comb. Theory B, 2012

Approximating rooted Steiner networks.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Approximating Minimum-Cost Connected T-Joins.

[BibT_eX]

[DOI]

Zachary Friggstad

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2009

Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs.

[BibT_eX]

[DOI]

Ashkan Aazami

Krishnam Raju Jampani

Proceedings of the Approximation, 2009

2008

On the integrality ratio for tree augmentation.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2008

2006

Network Design Via Iterative Rounding Of Setpair Relaxations.

[BibT_eX]

[DOI]

Marcelo Henriques de Carvalho

Comb., 2006

2005

An O(VE) algorithm for ear decompositions of matching-covered graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2005

Approximation algorithms for network design with metric costs.

[BibT_eX]

[DOI]

Marcelo Henriques de Carvalho

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

An O(VE) algorithm for ear decompositions of matching-covered graphs.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Packing Element-Disjoint Steiner Trees.

[BibT_eX]

[DOI]

Mohammad R. Salavatipour

Proceedings of the Approximation, 2005

2004

Hardness and Approximation Results for Packing Steiner Trees.

[BibT_eX]

[DOI]

Mohammad R. Salavatipour

Proceedings of the Algorithms, 2004

2003

An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

2002

Approximation algorithms for minimum-cost k-vertex connected subgraphs.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001

Approximating the Single-Sink Link-Installation Problem in Network Design.

[BibT_eX]

[DOI]

SIAM J. Optim., 2001

Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph.

[BibT_eX]

[DOI]

András Sebö

Zoltán Szigeti

SIAM J. Discret. Math., 2001

On Rooted Node-Connectivity Problems.

[BibT_eX]

[DOI]

Tibor Jordán

Zeev Nutov

Algorithmica, 2001

Edge Covers of Setpairs and the Iterative Rounding Method.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2001

Approximating Directed Multicuts.

[BibT_eX]

[DOI]

Howard J. Karloff

Yuval Rabani

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

1999

Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation.

[BibT_eX]

[DOI]

J. Algorithms, 1999

An Analysis of the Highest-Level Selection Rule in the Preflow-Push Max-Flow.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1999

On 2-Coverings and 2-Packings of Laminar Families.

[BibT_eX]

[DOI]

Tibor Jordán

R. Ravi

Proceedings of the Algorithms, 1999

1998

Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching

[BibT_eX]

Electron. Colloquium Comput. Complex., 1998

An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs.

[BibT_eX]

[DOI]

András Sebö

Zoltán Szigeti

Proceedings of the Integer Programming and Combinatorial Optimization, 1998

Approximating k-outconnected Subgraph Problems.

[BibT_eX]

[DOI]

Tibor Jordán

Zeev Nutov

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

1997

Hypercubes and Multicommodity Flows.

[BibT_eX]

[DOI]

Bo Yu

Penny E. Haxell

SIAM J. Discret. Math., 1997

Randomized Õ(M(|V|)) Algorithms for Problems in Matching Theory.

[BibT_eX]

[DOI]

SIAM J. Comput., 1997

The node multiterminal cut polyhedron.

[BibT_eX]

[DOI]

Bo Yu

Networks, 1997

Buy-at-Bulk Network Design: Approximating the Single-Sink Edge Installation Problem.

[BibT_eX]

[DOI]

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996

An o(n³)-Time Algorithm Maximum-Flow Algorithm.

[BibT_eX]

[DOI]

Torben Hagerup

SIAM J. Comput., 1996

Algorithms for Dense Graphs and Networks on the Random Access Computer.

[BibT_eX]

[DOI]

Algorithmica, 1996

Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

Approximation Algorithms for Feasible Cut and Multicut Problems.

[BibT_eX]

[DOI]

Bo Yu

Proceedings of the Algorithms, 1995

1994

Directed s-t Numberings, Rubber Bands, and Testing Digraph k-Vertex Connectivity.

[BibT_eX]

[DOI]

John H. Reif

Comb., 1994

A Las Vegas O(n2.38) Algorithm for the Cardinality of a Maximum Matching.

[BibT_eX]

[DOI]

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

Scan-First Search and Sparse Certificates: An Improved Parallel Algorithms for k-Vertex Connectivity.

[BibT_eX]

[DOI]

Ming-Yang Kao

SIAM J. Comput., 1993

Parallel and Output Sensitive Algorithms for Combinatorial and Linear Algebra Problems.

[BibT_eX]

[DOI]

John H. Reif

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

Random Weighted Laplacians, Lovász Minimum Digraphs and Finding Minimum Separators.

[BibT_eX]

[DOI]

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

A linear programming and rounding approach to max 2-sat.

[BibT_eX]

[DOI]

William H. Cunningham

Levent Tunçel

Yaoguang Wang

Proceedings of the Cliques, 1993

1992

Directed s-t Bumberings, Rubber Bands, and Testing Digraph k-Vertex Connectivity.

[BibT_eX]

[DOI]

John H. Reif

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

1991

Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

An Empirical Study of Min Cost Flow Algorithms for the Minimum-Cost Flow Problem.

[BibT_eX]

[DOI]

Proceedings of the Network Flows And Matching, 1991

1990

Can A Maximum Flow be Computed on o(nm) Time?

[BibT_eX]

[DOI]

Torben Hagerup

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1989

The Parallel Complexity of Finding a Blocking Flow in a 3-Layer Network.

[BibT_eX]

[DOI]

S. N. Maheshwari

Inf. Process. Lett., 1989

A Randomized Maximum-Flow Algorithm

[BibT_eX]

[DOI]

Torben Hagerup

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988

Finding Nonseparating Induced Cycles and Independent Spanning Trees in 3-Connected Graphs.

[BibT_eX]

[DOI]

S. N. Maheshwari

J. Algorithms, 1988

Analysis of Preflow Push Algorithms for Maximum Network Flow.

[BibT_eX]

[DOI]