4 papers
Distributed Dominating Set With Optimal Rounds and Message Size in Bounded Arboricity Graphs
Sharareh Alipour, Ermiya Farokhnejad
We study the distributed minimum dominating set problem on graphs of arboricity . Dory, Ghaffari, and Ilchi [PODC'22] showed that any algorithm achieving a constant or poly-log…
Robust Multiagent Collaboration Through Weighted Max-Min T-Joins
Sharareh Alipour
Many multiagent tasks -- such as reviewer assignment, coalition formation, or fair resource allocation -- require selecting a group of agents such that collaboration remains effect…
Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
Sharareh Alipour, Ermiya Farokhnejad, Tobias Mömke
We investigate semi-streaming algorithms for the Traveling Salesman Problem (TSP). Specifically, we focus on a variant known as the -TSP, where the distances between any two…
On the Ratio of Shannon Numbers of Graphs
Sharareh Alipour, Amin Gohari, Mehrshad Taziki
Let be a function that maps two arbitrary graphs and to a non-negative real number such that where is any…