research
∙
08/05/2023
A logarithmic approximation algorithm for the activation edge multicover problem
In the Activation Edge-Multicover problem we are given a multigraph G=(V...
share
research
∙
07/24/2023
A 1.5-pproximation algorithms for activating 2 disjoint st-paths
In the Activation k Disjoint st-Paths (Activation k-DP) problem we are g...
research
∙
07/17/2023
Extending the primal-dual 2-approximation algorithm beyond uncrossable set families
A set family F is uncrossable if A ∩ B,A ∪ B ∈ F or A ∖ B,B ∖ A ∈ F for ...
research
∙
07/04/2023
Improved approximation algorithms for some capacitated k edge connectivity problems
We consider the following two variants of the Capacitated k-Edge Connect...
research
∙
04/13/2023
Improved Approximations for Relative Survivable Network Design
One of the most important and well-studied settings for network design i...
research
∙
09/14/2022
Parameterized algorithms for node connectivity augmentation problems
A graph G is k-out-connected from its node s if it contains k internally...
research
∙
08/19/2022
An O(√(k))-approximation algorithm for minimum power k edge disjoint st -paths
In minimum power network design problems we are given an undirected grap...
research
∙
11/07/2021
k disjoint st-paths activation in polynomial time
In activation network design problems we are given an undirected graph G...
research
∙
10/18/2021
Data structure for node connectivity queries
Let κ(s,t) denote the maximum number of internally disjoint paths in an ...
research
∙
09/28/2020
Approximation algorithms for connectivity augmentation problems
In Connectivity Augmentation problems we are given a graph H=(V,E_H) and...
research
∙
09/21/2020
On rooted k-connectivity problems in quasi-bipartite digraphs
We consider the directed Rooted Subset k-Edge-Connectivity problem: give...
research
∙
07/09/2020
Practical Budgeted Submodular Maximization
We consider the Budgeted Submodular Maximization problem, that seeks to ...
research
∙
02/10/2020
2-node-connectivity network design
We consider network design problems in which we are given a graph G=(V,E...
research
∙
12/20/2019
An Õ(log^2 n)-approximation algorithm for 2-edge-connected dominating set
In the Connected Dominating Set problem we are given a graph G=(V,E) and...
research
∙
10/28/2019
Bounded Degree Group Steiner Tree Problems
We study two problems that seek a subtree T of a graph G=(V,E) such that...
research
∙
02/10/2019
Approximating k-connected m-dominating sets
A subset S of nodes in a graph G is a k-connected m-dominating set ((k,m...
research
∙
01/22/2019
A (4+ε)-approximation for k-connected subgraphs
We obtain approximation ratio 2(2+1/ℓ) for the (undirected) k-Connected ...
research
∙
12/24/2018