Approximation algorithms for multi-multiway cut and multicut problems on directed graphs | ||
| AUT Journal of Mathematics and Computing | ||
| مقاله 2، دوره 1، شماره 2، آذر 2020، صفحه 145-152 اصل مقاله (383.18 K) | ||
| نوع مقاله: Original Article | ||
| شناسه دیجیتال (DOI): 10.22060/ajmc.2018.15109.1014 | ||
| نویسندگان | ||
| Ramin Yarinezhad؛ Seyed Naser Hashemi* | ||
| Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran | ||
| چکیده | ||
| In this paper, we study the directed multicut and directed multimultiway 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,\cdots, 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),\cdots,(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 si to ti . 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. | ||
| کلیدواژهها | ||
| Approximation algorithm؛ Complexity؛ NP-hard problems؛ Directed multi-multiway cut؛ Directed multicut cut | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 2,861 تعداد دریافت فایل اصل مقاله: 3,165 |
||
| تعداد نشریات | 9 |
| تعداد شمارهها | 455 |
| تعداد مقالات | 5,772 |
| تعداد مشاهده مقاله | 8,413,477 |
| تعداد دریافت فایل اصل مقاله | 6,973,705 |