|
Iranian Journal of Mathematical Sciences and Informatics، جلد ۱۷، شماره ۲، صفحات ۲۵۳-۲۷۱
|
|
|
عنوان فارسی |
|
|
چکیده فارسی مقاله |
|
|
کلیدواژههای فارسی مقاله |
|
|
عنوان انگلیسی |
Logical s-t Min-Cut Problem: An Extension to the Classic s-t Min-Cut Problem |
|
چکیده انگلیسی مقاله |
Let $G$ be a weighted digraph, $s$ and $t$ be two vertices of $G$, and $t$ is reachable from $s$. The logical $s$-$t$ min-cut (LSTMC) problem states how $t$ can be made unreachable from $s$ by removal of some edges of $G$ where (a) the sum of weights of the removed edges is minimum and (b) all outgoing edges of any vertex of $G$ cannot be removed together. If we ignore the second constraint, called the logical removal, the LSTMC problem is transformed to the classic $s$-$t$ min-cut problem. The logical removal constraint applies in situations where non-logical removal is either infeasible or undesired. Although the $s$-$t$ min-cut problem is solvable in polynomial time by the max-flow min-cut theorem, this paper shows the LSTMC problem is NP-Hard, even if $G$ is a DAG with an out-degree of two. Moreover, this paper shows that the LSTMC problem cannot be approximated within $alpha log n$ in a DAG with $n$ vertices for some constant $alpha$. The application of the LSTMC problem is also presented intest case generation of a computer program. |
|
کلیدواژههای انگلیسی مقاله |
Logical s-t min-cut, LSTMC, Complexity, Inapproximability, Flow graph, Test case generation. |
|
نویسندگان مقاله |
| M. Valizadeh Faculty of Information Technology, Iran Telecommunication Research Center (ITRC), P.O.Box:14155-3961, Tehran, Iran
| M. H. Tadayon Faculty of Information Technology, Iran Telecommunication Research Center (ITRC), P.O.Box:14155-3961, Tehran, Iran
|
|
نشانی اینترنتی |
http://ijmsi.ir/browse.php?a_code=A-10-4287-1&slc_lang=en&sid=1 |
فایل مقاله |
فایلی برای مقاله ذخیره نشده است |
کد مقاله (doi) |
|
زبان مقاله منتشر شده |
en |
موضوعات مقاله منتشر شده |
عمومی |
نوع مقاله منتشر شده |
پژوهشی |
|
|
برگشت به:
صفحه اول پایگاه |
نسخه مرتبط |
نشریه مرتبط |
فهرست نشریات
|