Sahand MozaffariPh.D. Candidatein the Theory and Algorithms Group of Computer Science Department of University of Illinois at Urbana-Champaign |
My name is Sahand Mozaffari, natively written سهند مظفری and pronounced sæhænd mozæfæɾiː. Currently, I am pursuing a Ph.D. in Computer Science at University of Illinois at Urbana-Champaign. Previously, I have received B.S. degrees in Computer Engineering and in Theoretical Mathematics from Sharif University of Technology.
We investigate the odd multiway node (edge) cut problem where the input is a graph with a specified collection of terminal nodes and the goal is to find a smallest subset of non-terminal nodes (edges) to delete so that the terminal nodes do not have an odd length path between them. In an earlier work, Lokshtanov and Ramanujan showed that both odd multiway node cut and odd multiway edge cut are fixed-parameter tractable (FPT) when parameterized by the size of the solution in undirected graphs. In this work, we focus on directed acyclic graphs (DAGs) and design a fixed-parameter algorithm. Our main contribution is an extension of the shadow-removal framework for parity problems in DAGs. We complement our FPT results with tight approximability as well as polyhedral results for 2 terminals in DAGs. Additionally, we show inapproximability results for odd multiway edge cut in undirected graphs even for 2 terminals.
Let \(G\) be a graph. A total dominating set of \(G\) is a set \(S\) of vertices of \(G\) such that every vertex is adjacent to at least one vertex in \(S\). The total domatic number of a graph is the maximum number of total dominating sets which partition the vertex set of \(G\). In this paper we provide a criterion under which a cubic graph has total domatic number at least two.
In this thesis, we discuss the facility location problem in two-dimensional space. Facility location problem, also known as k-center problem, is of great importance in computational geometry, operational research and data mining fields. The goal in this problem is to find an optimum placement for k facilities on the plane, such that the cost for clients traveling to the nearest facility is minimized. Solving this problem in presence of outlier points has interested many researchers in recent years.
In this article, having explained the previous works on this subject, we present new algorithms for k-center problem with weighted outliers.