TY - JOUR
ID - 20104
TI - Making problem: A new approach to reachability assurance in digraphs
JO - Scientia Iranica
JA - SCI
LA - en
SN - 1026-3098
AU - Valizadeh, M.
AU - Tadayon, M.H.
AU - Bagheri, A.
AD - Iran Telecommunication Research Center (ITRC), Tehran, Iran
AD - Faculty of Computer Engineering, Amirkabir University of Technology, Tehran, Iran
Y1 - 2018
PY - 2018
VL - 25
IS - 3
SP - 1441
EP - 1455
KW - Marking problem
KW - Reachability assurance
KW - Pathfinding
KW - Software testing
DO - 10.24200/sci.2018.20104
N2 - Let G be a weighted digraph and s and t be two vertices of G. The reachability assurance (RA) problem is how to label the edges of G such that every path starting at s finally reaches t and the sum of the weights of the labeled edges, called the RA cost, is minimal. The common approach to the RA problem is pathfinding, in which a path is sought from s to t and then the edges of the path are labeled. This paper introduces a new approach, the marking problem (MP), to the RA problem. Compared to the common pathfinding approach, the proposed MP approach has a lower RA cost. It is shown that the MP is NP-complete, even when the underlying digraph is an unweighted directed acyclic graph (DAG) or a weighted DAG with an out-degree of two. An appropriate heuristic algorithm to solve the MP in polynomial time is provided. To mitigate the RA problem as a serious challenge in this area, application of the MP in software testing is also presented. By evaluating the datasets from various program flow graphs, it is shown that the MP is superior to the pathfinding in the context of test case generation.
UR - http://scientiairanica.sharif.edu/article_20104.html
L1 - http://scientiairanica.sharif.edu/article_20104_b6f1e6f3b30f26b5f2a22c3621fe6f97.pdf
ER -