13 citations · 19 across the 11 of their papers we have counts for
16 papers
Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
Saeed Amiri, Sebastian Siebertz
For every fixed proper minor-closed class and every , we give a deterministic LOCAL algorithm that returns a dominating set of size at most $(2a(\mathscr C)+1+ε)γ…
Deterministic CONGEST Algorithm for MDS on Bounded Arboricity Graphs
Saeed Akhoondian Amiri
We provide a deterministic CONGEST algorithm to constant factor approximate the minimum dominating set on graphs of bounded arboricity in rounds. This improves over the…
On Fine-Grained Exact Computation in Regular Graphs
Saeed Akhoondian Amiri
We show that there is no subexponential time algorithm for computing the exact solution of the maximum independent set problem in d-regular graphs unless ETH fails. We expand our m…
Disjoint Shortest Paths with Congestion on DAGs
Saeed Akhoondian Amiri, Julian Wargalla
In the k-Disjoint Shortest Paths problem, a set of terminal pairs of vertices is given and we are asked to find paths such that eac…
Distributed Distance- Dominating Set on Sparse High-Girth Graphs
Saeed Akhoondian Amiri, Ben Wiederhake
The dominating set problem and its generalization, the distance- dominating set problem, are among the well-studied problems in the sequential settings. In distributed models of…
Complexity of Computing the Anti-Ramsey Numbers for Paths
Saeed Akhoondian Amiri, Alexandru Popa, Mohammad Roghani +3
The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erd\" os, Simonovits and S\' os. For given graphs and the \emph{anti-Ramsey number}…
Short Schedules for Fast Flow Rerouting
Saeed Akhoondian Amiri, Szymon Dudycz, Mahmoud Parham +2
This paper studies the fundamental problem of how to reroute unsplittable flows of a certain demand in a capacitated network from their current paths to their respective new pa…
Distributed Dominating Set Approximations beyond Planar Graphs
Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz
The Minimum Dominating Set (MDS) problem is one of the most fundamental and challenging problems in distributed computing. While it is well-known that minimum dominating sets canno…
Charting the Complexity Landscape of Waypoint Routing
Saeed Akhoondian Amiri, Klaus-Tycho Foerster, Riko Jacob +1
Modern computer networks support interesting new routing models in which traffic flows from a source s to a destination t can be flexibly steered through a sequence of waypoints, s…
Congestion-Free Rerouting of Flows on DAGs
Saeed Akhoondian Amiri, Szymon Dudycz, Stefan Schmid +1
Changing a given configuration in a graph into another one is known as a re- configuration problem. Such problems have recently received much interest in the context of algorithmic…
Transiently Consistent SDN Updates: Being Greedy is Hard
Saeed Akhoondian Amiri, Arne Ludwig, Jan Marcinkowski +1
The software-defined networking paradigm introduces interesting opportunities to operate networks in a more flexible, optimized, yet formally verifiable manner. Despite the logical…
Routing with Congestion in Acyclic Digraphs
Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx +1
We study the version of the -disjoint paths problem where demand pairs , , are specified in the input and the paths in the solution are allowed…
The Erdos-Posa Property for Directed Graphs
Saeed Akhoondian Amiri, Ken-Ichi Kawarabayashi, Stephan Kreutzer +1
A classical result by Erdos and Posa states that there is a function such that for every , every graph contains pairwise vertex…
A local constant factor approximation for the minimum dominating set problem on bounded genus graphs
Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz
The Minimum Dominating Set (MDS) problem is not only one of the most fundamental problems in distributed computing, it is also one of the most challenging ones. While it is well-kn…
DAG-width is PSPACE-complete
Saeed Akhoondian Amiri, Stephan Kreutzer, Roman Rabinovich
Berwanger et al. show that for every graph of size and DAG-width there is a DAG decomposition of width and size . This gives a polynomial time algorithm f…
Vertex Disjoint Path in Upward Planar Graphs
Saeed Amiri, Ali Golshani, Stephan Kreutzer +1
The -vertex disjoint paths problem is one of the most studied problems in algorithmic graph theory. In 1994, Schrijver proved that the problem can be solved in polynomial time f…