2 citations · 4 across the 13 of their papers we have counts for
16 papers
An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
Afrouz Jabal Ameli, Yusuke Kobayashi, Takashi Noguchi
In the 2-Vertex-Connected Spanning Subgraph problem (2-VCSS), we are given an undirected graph , and the objective is to find a 2-vertex-connected spanning subgraph of w…
New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof +1
The Strongly Connected Steiner Subgraph (SCSS) problem is a well-studied network design problem that asks for a minimum subgraph that strongly connects a given set of terminals. In…
Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
Afrouz Jabal Ameli, Jesper Nederlof, Shengzhe Wang
We provide improved space-time tradeoffs for permutation problems over additively idempotent semi-rings. In particular, there is an algorithm for the Traveling Salesperson Problem…
Learning-Augmented Online Covering Problems
Afrouz Jabal Ameli, Laura Sanita, Moritz Venzin
We give a very general and simple framework to incorporate predictions on requests for online covering problems in a rigorous and black-box manner. Our framework turns any online a…
On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum
Afrouz Jabal Ameli, Faezeh Motiei, Morteza Saghafian
Given a finite set of red and blue points in $\Rspace^d$, the MST-ratio is defined as the total length of the Euclidean minimum spanning trees of the red points and the blue points…
A -Approximation for Two-Edge Connectivity
Miguel Bosch-Calvo, Mohit Garg, Fabrizio Grandoni +3
The 2-Edge-Connected Spanning Subgraph problem (2ECSS) is among the most basic survivable network design problems: given an undirected and unweighted graph, the task is to find a s…
Improved Approximations for Flexible Network Design
Dylan Hyatt-Denesik, Afrouz Jabal Ameli, Laura Sanita
Flexible network design deals with building a network that guarantees some connectivity requirements between its vertices, even when some of its elements (like vertices or edges) f…
The clique number of the exact distance -power graph: complexity and eigenvalue bounds
Aida Abiad, Afrouz Jabal Ameli, Luuk Reijnders
The exact distance -power of a graph , , is a graph which has the same vertex set as , with two vertices adjacent in if and only if they a…
Node Connectivity Augmentation of Highly Connected Graphs
Waldo Galvez, Dylan Hyatt-Denesik, Afrouz Jabal Ameli +1
Node-connectivity augmentation is a fundamental network design problem. We are given a -node connected graph together with an additional set of links, and the goal is to add…
A PTAS for Triangle-Free 2-Matching
Miguel Bosch-Calvo, Fabrizio Grandoni, Afrouz Jabal Ameli
In the Triangle-Free (Simple) 2-Matching problem we are given an undirected graph . Our goal is to compute a maximum-cardinality satisfying the following pr…
A Approximation for -Vertex-Connectivity
Miguel Bosch-Calvo, Fabrizio Grandoni, Afrouz Jabal Ameli
The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph . Ou…
Finding Almost Tight Witness Trees
Dylan Hyatt-Denesik, Afrouz Jabal Ameli, Laura Sanità
This paper addresses a graph optimization problem, called the Witness Tree problem, which seeks a spanning tree of a graph minimizing a certain non-linear objective function. This…
Improved Approximation for Two-Edge-Connectivity
Mohit Garg, Fabrizio Grandoni, Afrouz Jabal Ameli
The basic goal of survivable network design is to construct low-cost networks which preserve a sufficient level of connectivity despite the failure or removal of a few nodes or edg…
Breaching the 2-Approximation Barrier for the Forest Augmentation Problem
Fabrizio Grandoni, Afrouz Jabal Ameli, Vera Traub
The basic goal of survivable network design is to build cheap networks that guarantee the connectivity of certain pairs of nodes despite the failure of a few edges or nodes. A cele…
Approximation Algorithms for Demand Strip Packing
Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli +1
In the Demand Strip Packing problem (DSP), we are given a time interval and a collection of tasks, each characterized by a processing time and a demand for a given resource (such a…
Breaching the 2-Approximation Barrier for Connectivity Augmentation: a Reduction to Steiner Tree
Jarosław Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli
The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The Co…