دوره 17، شماره 2 - ( 6-1401 )                   جلد 17 شماره 2 صفحات 271-253 | برگشت به فهرست نسخه ها


XML Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Valizadeh M, Tadayon M H. Logical s-t Min-Cut Problem: An Extension to the Classic s-t Min-Cut Problem. IJMSI 2022; 17 (2) :253-271
URL: http://ijmsi.ir/article-1-1481-fa.html
Logical s-t Min-Cut Problem: An Extension to the Classic s-t Min-Cut Problem. مجله علوم ریاضی و انفورماتیک. 1401; 17 (2) :253-271

URL: http://ijmsi.ir/article-1-1481-fa.html


چکیده:  
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.
نوع مطالعه: پژوهشي | موضوع مقاله: عمومى

ارسال نظر درباره این مقاله : نام کاربری یا پست الکترونیک شما:
CAPTCHA

بازنشر اطلاعات
Creative Commons License این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است.

کلیه حقوق این وب سایت متعلق به نشریه علوم ریاضی و انفورماتیک می باشد.

طراحی و برنامه نویسی : یکتاوب افزار شرق

© 2024 CC BY-NC 4.0 | Iranian Journal of Mathematical Sciences and Informatics

Designed & Developed by : Yektaweb