TY - JOUR
ID - 3810
TI - Approximation algorithms for multi-multiway cut and multicut problems on directed graphs
JO - AUT Journal of Mathematics and Computing
JA - AJMC
LA - en
SN -
AU - Yarinezhad, Ramin
AU - Hashemi, Seyed Naser
AD - Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran
Y1 - 2020
PY - 2020
VL - 1
IS - 2
SP - 145
EP - 152
KW - Approximation algorithm
KW - Computational complexity
KW - NP-hard problems
KW - Directed multi-multiway cut
KW - Directed multicut cut
DO - 10.22060/ajmc.2018.15109.1014
N2 - In this paper, we study the directed multicut and directed multi-multiway cut problems. The input to the directed multi-multiway cut problem is a weighted directed graph $G=(V,E)$ and $k$ sets $S_1,S_2,...,S_k$ of vertices. The goal is to find a subset of edges of minimum total weight whose removal will disconnect all the connections between the vertices in each set $S_i$, for $1 leq i leq k$. A special case of this problem is the directed multicut problem whose input consists of a weighted directed graph $G=(V,E)$ and a set of ordered pairs of vertices $(s_1,t_1),...,(s_k,t_k)$. The goal is to find a subset of edges of minimum total weight whose removal will make for any $i, 1 leq i leq k, $ there is no directed path from $s_i$ to $t_i$.In this paper, we present two approximation algorithms for these problems. The so called region growing paradigm is modified and used for these two cut problems on directed graphs. using this paradigm, we give an approximation algorithm for each problem such that both algorithms have the approximation factor of $O(k)$ the same as the previous works done on these problems. However, the previous works need to solve $k$ linear programming, whereas our algorithms require only one linear programming. Therefore, our algorithms improve the running time of the previous algorithms.
UR - https://ajmc.aut.ac.ir/article_3810.html
L1 - https://ajmc.aut.ac.ir/article_3810_5e4da5297ba5154b4c1b08186e4dbb8e.pdf
ER -