3 citations · 11 across the 14 of their papers we have counts for
19 papers
Semi-Streaming Estimation of the Held--Karp Bound and Graph-Metric TSP Cost
Sharareh Alipour
The Held--Karp bound is a linear-programming lower bound for the metric traveling salesperson problem (TSP). We approximate this bound in the multi-pass insertion-only streaming mo…
Sublinear-Time and Semi-Streaming Algorithms for Path Cover and TSP
Sharareh Alipour, Ali Nowzari
We give improved sublinear-time and semi-streaming approximation algorithms for maximum path cover, -TSP, and Max-TSP. For each fixed $\eps>0$, our distance-query algorithm…
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-loga…
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 natu…
On distributed algorithms for minimum dominating set problem and beyond
Sharareh Alipour, Mohammadhadi Salari
In this paper, we study the minimum dominating set (MDS) problem and the minimum total dominating set MTDS) problem which have many applications in real world. We propose a new ide…
On Planar Visibility Counting Problem
Sharareh Alipour
For a set of disjoint line segments in , the visibility counting problem is to preprocess such that the number of visible segments in from any query…
On guarding polygons with holes
Sharareh Alipour
There is an old conjecture by Shermer \cite{sher} that in a polygon with vertices and holes, vertex guards are sufficient to guard the enti…
On Distributed Algorithms for Minimum Dominating Set problem, from theory to application
Sharareh Alipour, Ehsan Futuhi, Shayan Karimi
In this paper, we propose a distributed algorithm for the minimum dominating set problem. For some especial networks, we prove theoretically that the achieved answer by our propose…
On decomposing complete tripartite graphs into 5-cycles
M. Abdolmaleki, S. Gh. Ilchi, E. S. Mahmoodian +1
The problem of finding necessary and sufficient conditions to decompose a complete tripartite graph into 5-cycles was first considered by E.S. Mahmoodian and Maryam Mir…
Improved constant approximation factor algorithms for -center problem for uncertain data
Sharareh Alipour
In real applications, database systems should be able to manage and process data with uncertainty. Any real dataset may have missing or rounded values, also the values of data may…
On Triangluar Separation of Bichromatic Point Sets in Polygonal Environment
Farnaz Sheikhi, Sharareh Alipour
Let be a simple polygonal environment with vertices in the plane. Assume that a set of blue points and a set of red points are distributed in $\mat…
Hardness of Segment Cover, Contiguous SAT and Visibility with Uncertain Obstacles
Sharareh Alipour, Salman Parsa
We define the problem segment cover as follows. We are given a set of pairs of sub-intervals of the unit interval. The problem asks if there is a choice of a single interval from e…
Upper bounds for domination numbers of graphs using Turán's Theorem and Lovász local lemma
Sharareh Alipour, Amir Jafari
Let be a connected graph of order with vertex set . A subset is an -dominating set if every vertex is adjacent to at least verti…
On -tuple and -tuple total domination numbers of regular graphs
Sharareh Alipour, Amir Jafari, Morteza Saghafian
Let be a connected graph of order , whose minimum vertex degree is at least . A subset of vertices in is a -tuple total dominating set if every vertex of i…
Improvements on the k-center problem for uncertain data
Sharareh Alipour, Amir Jafari
In real applications, there are situations where we need to model some problems based on uncertain data. This leads us to define an uncertain model for some classical geometric opt…
An improved Constant-Factor Approximation Algorithm for Planar Visibility Counting Problem
Sharareh Alipour, Mohammad Ghodsi, Amir Jafari
Given a set of disjoint line segments in , the visibility counting problem (VCP) is to preprocess such that the number of segments in visible from a…
Fast Approximation and Randomized Algorithms for Diameter
Sharareh Alipour, Bahman Kalantari, Hamid Homapour
We consider approximation of diameter of a set of points in dimension . Eeciolu and Kalantari \cite{kal} have shown that given any , by co…