13 citations · 19 across the 11 of their papers we have counts for
7 papers · 1 filter
Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short Broadcasts
Saeed Amiri, Sebastian Siebertz, Wojciech Wawrzyniak
We present a general framework for deterministic constant-round approximation of covering problems in sparse networks in the broadcast CONGEST model, where every vertex broadcasts…
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…
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…
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…
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…
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…