Zeev Nutov

CoRR, July, 2025

Bicriteria approximation for k-edge-connectivity.

[BibT_eX]

[DOI]

Reut Cohen

CoRR, July, 2025

A 22k-approximation algorithm for minimum power k edge disjoint st-paths.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2025

Tight Analysis of the Primal-Dual Method for Edge-Covering Pliable Set Families.

[BibT_eX]

[DOI]

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

Bicriteria Approximation for k-Edge-Connectivity.

[BibT_eX]

[DOI]

Reut Cohen

Proceedings of the 33rd Annual European Symposium on Algorithms, 2025

2024

Approximation algorithms for node and element connectivity augmentation problems.

[BibT_eX]

[DOI]

Theory Comput. Syst., October, 2024

Improved approximation ratio for covering pliable set families.

[BibT_eX]

[DOI]

CoRR, 2024

Improved Approximation Algorithms for Covering Pliable Set Families and Flexible Graph Connectivity.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 22nd International Workshop, 2024

Extending the Primal-Dual 2-Approximation Algorithm Beyond Uncrossable Set Families.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2024

Parameterized Algorithms for Node Connectivity Augmentation Problems.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

A 1.5-Approximation Algorithm for Activating Two Disjoint st-Paths.

[BibT_eX]

[DOI]

Dawod Kahba

Proceedings of the Algorithmics of Wireless Networks - 20th International Symposium, 2024

2023

Covering Users With QoS by a Connected Swarm of Drones: Graph Theoretical Approach and Experiments.

[BibT_eX]

[DOI]

Kiril Danilchenko

IEEE/ACM Trans. Netw., December, 2023

Practical Budgeted Submodular Maximization.

[BibT_eX]

[DOI]

Moran Feldman

Elad Shoham

Algorithmica, May, 2023

Doing their best: How to provide service by limited number of drones?

[BibT_eX]

[DOI]

Kiril Danilchenko

Wirel. Networks, 2023

A logarithmic approximation algorithm for the activation edge multicover problem.

[BibT_eX]

[DOI]

CoRR, 2023

A 1.5-pproximation algorithms for activating 2 disjoint st-paths.

[BibT_eX]

[DOI]

Dawod Kahba

CoRR, 2023

Improved approximation algorithms for some capacitated k edge connectivity problems.

[BibT_eX]

[DOI]

CoRR, 2023

Improved Approximations for Relative Survivable Network Design.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 21st International Workshop, 2023

An $O(\sqrt{k})$-Approximation Algorithm for Minimum Power k Edge Disjoint st-Paths.

[BibT_eX]

[DOI]

Proceedings of the Unity of Logic and Computation, 2023

2022

A 4 + ϵ approximation for k-connected subgraphs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2022

A polylogarithmic approximation algorithm for 2-edge-connected dominating set.

[BibT_eX]

[DOI]

Amir Belgi

Inf. Process. Lett., 2022

The minimum degree Group Steiner problem.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2022

Data Structures for Node Connectivity Queries.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Data structure for node connectivity queries.

[BibT_eX]

[DOI]

CoRR, 2021

On Rooted k-Connectivity Problems in Quasi-bipartite Digraphs.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2021

Approximation Algorithms for Connectivity Augmentation Problems.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2021

2020

Practical Budgeted Submodular Maximization.

[BibT_eX]

[DOI]

Elad Shoham

CoRR, 2020

2-Node-Connectivity Network Design.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 18th International Workshop, 2020

A 4 + ε approximation for k-connected subgraphs.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Bounded Degree Group Steiner Tree Problems.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 31st International Workshop, 2020

Approximating k-Connected m-Dominating Sets.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Covering Users by a Connected Swarm Efficiently.

[BibT_eX]

[DOI]

Kiril Danilchenko

Proceedings of the Algorithms for Sensor Systems, 2020

2019

An Õ(log2n)-approximation algorithm for 2-edge-connected dominating set.

[BibT_eX]

[DOI]

Amir Belgi

CoRR, 2019

A (4+ε)-approximation for k-connected subgraphs.

[BibT_eX]

[DOI]

CoRR, 2019

Approximating Activation Edge-Cover and Facility Location Problems.

[BibT_eX]

[DOI]

Eli Shalom

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018

Erratum: Approximating Minimum-Cost Connectivity Problems via Uncrossable Bifamilies.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Improved Approximation Algorithms for Minimum Cost Node-Connectivity Augmentation Problems.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2018

Improved approximation algorithms for k-connected m-dominating set problems.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2018

Approximating activation edge-cover and facility location problems.

[BibT_eX]

[DOI]

Eli Shalom

CoRR, 2018

Improved Approximation Algorithms for Minimum Power Covering Problems.

[BibT_eX]

[DOI]

Gruia Calinescu

Proceedings of the Approximation and Online Algorithms - 16th International Workshop, 2018

Activation Network Design Problems.

[BibT_eX]

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

Node-Connectivity Survivable Network Problems.

[BibT_eX]

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

The k-Connected Subgraph Problem.

[BibT_eX]

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

2017

Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights.

[BibT_eX]

[DOI]

Michael Dinitz

ACM Trans. Algorithms, 2017

A Note on the Tree Augmentation Problem.

[BibT_eX]

[DOI]

CoRR, 2017

Improved approximation algorithms for k-connected m-dominating set problems.

[BibT_eX]

[DOI]

CoRR, 2017

On the Tree Augmentation Problem.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2016

LP-Relaxations for Tree Augmentation.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design.

[BibT_eX]

[DOI]

Takuro Fukunaga

R. Ravi

SIAM J. Comput., 2015

A 1.75 LP approximation for the Tree Augmentation Problem.

[BibT_eX]

[DOI]

CoRR, 2015

Approximating Source Location and Star Survivable Network Problems.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2015

2014

Approximating minimum-cost edge-covers of crossing biset-families.

[BibT_eX]

[DOI]

Comb., 2014

Degree Constrained Node-Connectivity Problems.

[BibT_eX]

[DOI]

Algorithmica, 2014

Approximating Steiner Trees and Forests with Minimum Number of Steiner Points.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 12th International Workshop, 2014

Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights.

[BibT_eX]

[DOI]

Michael Dinitz

Proceedings of the Approximation, 2014

2013

MMM: multi-channel TDMA with MPR capabilities for MANETs.

[BibT_eX]

[DOI]

Shimon Avadis

Anat Lerner

Wirel. Networks, 2013

A (1+ln2)(1+ln2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

On some network design problems with degree constraints.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2013

Small ℓℓ-edge-covers in kk-connected graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2013

Approximating {0,1,2}-Survivable Networks with Minimum Number of Steiner Points

[BibT_eX]

[DOI]

CoRR, 2013

On Fixed Cost k-Flow Problems.

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

Proceedings of the Approximation and Online Algorithms - 11th International Workshop, 2013

2012

Approximating minimum-cost connectivity problems via uncrossable bifamilies.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

A note on labeling schemes for graph connectivity.

[BibT_eX]

[DOI]

Rani Izsak

Inf. Process. Lett., 2012

A unified approach to source location via rooted network augmentation

[BibT_eX]

[DOI]

CoRR, 2012

Small ℓ-edge-covers in k-connected graphs

[BibT_eX]

[DOI]

CoRR, 2012

Scheduling of Vehicles in Transportation Networks.

[BibT_eX]

[DOI]

Dariusz R. Kowalski

Proceedings of the Communication Technologies for Vehicles - 4th International Workshop, 2012

Survivable Network Activation Problems.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Degree-Constrained Node-Connectivity.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Steiner Forest Orientation Problems.

[BibT_eX]

[DOI]

Marek Cygan

Proceedings of the Algorithms - ESA 2012, 2012

Approximating Minimum Power Edge-Multi-Covers.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2012

2011

Approximating survivable networks with β-metric costs.

[BibT_eX]

[DOI]

Johnny David

J. Discrete Algorithms, 2011

A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2.

[BibT_eX]

[DOI]

Guy Even

Inf. Process. Lett., 2011

Combinatorial Algorithms for Capacitated Network Design

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

CoRR, 2011

Approximating minimum-power edge-multicovers

[BibT_eX]

[DOI]

CoRR, 2011

Approximating Subset k-Connectivity Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 9th International Workshop, 2011

Network-Design with Degree Constraints.

[BibT_eX]

[DOI]

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

A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius.

[BibT_eX]

[DOI]

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

2010

Approximating minimum power covers of intersecting families and directed edge-connectivity problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Covering a laminar family by leaf to leaf links.

[BibT_eX]

[DOI]

Yael Maduel

Discret. Appl. Math., 2010

Approximating Survivable Networks with Minimum Number of Steiner Points.

[BibT_eX]

[DOI]

Lior Kamma

Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

Prize-Collecting Steiner Network Problems.

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2009

A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

Wireless network design via 3-decompositions.

[BibT_eX]

[DOI]

Ariel Yaroshevitch

Inf. Process. Lett., 2009

A note on Rooted Survivable Networks.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

Listing minimal edge-covers of intersecting families with applications to connectivity problems.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

Approximating minimum-power edge-covers and 2, 3-connectivity.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

An almost O(log k)-approximation for k-connected subgraphs.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Improved approximating algorithms for Directed Steiner Forest.

[BibT_eX]

[DOI]

Moran Feldman

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Approximating Fault-Tolerant Group-Steiner Problems.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Approximating minimum cost connectivity problems.

[BibT_eX]

[DOI]

Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009

Approximating Node-Connectivity Augmentation Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

Approximating Some Network Design Problems with Node Costs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

Improved Approximation Algorithms for Maximum Lifetime Problems in Wireless Networks.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2009

2008

A note on two source location problems.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2008

Approximating maximum satisfiable subsystems of linear equations of bounded width.

[BibT_eX]

[DOI]

Daniel Reichman

Inf. Process. Lett., 2008

On extremal k-outconnected graphs.

[BibT_eX]

[DOI]

Discret. Math., 2008

Approximating Steiner Networks with Node Weights.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Approximating Minimum-Power Degree and Connectivity Problems.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Approximating maximum integral flows in wireless sensor networks via weighted-degree constrained k-flows.

[BibT_eX]

[DOI]

Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing, 2008

Approximating Directed Weighted-Degree Constrained Networks.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2008

Inapproximability of Survivable Networks.

[BibT_eX]

[DOI]

Yuval Lando

Proceedings of the Approximation, 2008

Approximating Maximum Subgraphs without Short Cycles.

[BibT_eX]

[DOI]

Michael Langberg

Proceedings of the Approximation, 2008

Approximating Minimum-Power k-Connectivity.

[BibT_eX]

[DOI]

Proceedings of the Ad-hoc, Mobile and Wireless Networks, 7th International Conference, 2008

Novel Algorithms for the Network Lifetime Problem in Wireless Settings.

[BibT_eX]

[DOI]

Proceedings of the Ad-hoc, Mobile and Wireless Networks, 7th International Conference, 2008

2007

Approximating Minimum-Cost Connectivity Problems.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

Approximation algorithms and hardness results for cycle packing problems.

[BibT_eX]

[DOI]

Michael Krivelevich

Mohammad R. Salavatipour

Jacques Verstraëte

ACM Trans. Algorithms, 2007

On shredders and vertex connectivity augmentation.

[BibT_eX]

[DOI]

Gilad Liberman

J. Discrete Algorithms, 2007

Improved approximation algorithms for directed Steiner forest.

[BibT_eX]

[DOI]

Moran Feldman

Electron. Colloquium Comput. Complex., 2007

On (t, k)-shredders in k-connected graphs.

[BibT_eX]

Masao Tsugaki

Ars Comb., 2007

On Minimum Power Connectivity Problems.

[BibT_eX]

[DOI]

Yuval Lando

Proceedings of the Algorithms, 2007

Approximating Interval Scheduling Problems with Bounded Profits.

[BibT_eX]

[DOI]

Israel Beniaminy

Meir Ovadia

Proceedings of the Algorithms, 2007

2006

A (1-1/e)-approximation algorithm for the generalized assignment problem.

[BibT_eX]

[DOI]

Israel Beniaminy

Oper. Res. Lett., 2006

Tight Approximation Algorithm for Connectivity Augmentation Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2006

2005

Approximating k-node Connected Subgraphs via Critical Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Greedy approximation algorithms for directed multicuts.

[BibT_eX]

[DOI]

Yana Kortsarts

Networks, 2005

Approximating connectivity augmentation problems.

[BibT_eX]

[DOI]

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

Approximation algorithms for cycle packing problems.

[BibT_eX]

[DOI]

Michael Krivelevich

Mohammad Taghi Hajiaghayi

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

Power Optimization for Connectivity Problems.

[BibT_eX]

[DOI]

Vahab S. Mirrokni

Proceedings of the Integer Programming and Combinatorial Optimization, 2005

2004

Approximation Algorithm for Directed Multicuts.

[BibT_eX]

[DOI]

Yana Kortsarts

Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

Approximation algorithm for k-node connected subgraphs via critical graphs.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Packing Directed Cycles Efficiently.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

2003

Approximating Rooted Connectivity Augmentation Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2003

2001

On Rooted Node-Connectivity Problems.

[BibT_eX]

[DOI]

Joseph Cheriyan

Tibor Jordán

Algorithmica, 2001

A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2001

2000

On Integrality, Stability and Composition of Dicycle Packings and Covers.

[BibT_eX]

[DOI]

Michal Penn

J. Comb. Optim., 2000

Approximating node connectivity problems via set covers.

[BibT_eX]

[DOI]

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999

A 3-Approximation Algorithm for Finding Optimum 4, 5-Vertex-Connected Spanning Subgraphs.

[BibT_eX]

[DOI]

Yefim Dinitz

J. Algorithms, 1999

A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph.

[BibT_eX]

[DOI]

J. Algorithms, 1999

Approximating Multiroot 3-Outconnected Subgraphs.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998

Approximating k-outconnected Subgraph Problems.

[BibT_eX]

[DOI]

Joseph Cheriyan

Tibor Jordán

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

1997

Faster approximation algorithms for weighted triconnectivity augmentation problems.

[BibT_eX]

[DOI]

Michal Penn

Oper. Res. Lett., 1997

Finding Optimum k-vertex Connected Spanning Subgraphs: Improved Approximation Algorithms for k=3, 4, 5.

[BibT_eX]

[DOI]

Yefim Dinitz

Proceedings of the Algorithms and Complexity, Third Italian Conference, 1997

1995

on the Integral Dicycle Packings and Covers and the Linear ordering Polytope.

[BibT_eX]

[DOI]

Michal Penn

Discret. Appl. Math., 1995

A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance.

[BibT_eX]

[DOI]

Yefim Dinitz