Corrigendum to: “Making problem: A new approach to reachability assurance in digraphs”[Scientia Iranica 25(3) (2018) 1441-1455]

Document Type : Article

Author

--------

Abstract

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.

Keywords

References

  1. Corrigendum to: “Making problem: A new approach to reachability assurance in digraphs”[Scientia Iranica 25(3) (2018) 1441-1455]
  2. Design of Alternating Magnetic Field Generator for Magnetic Fluid Hyperthermia Research ApplicatioN
  3. 1. Krokhmal, P. and Uryasev, S. \Portfolio optimization
    with conditional value-at-risk objective and constraints",
    J. Risk, 4, pp. 11-27 (2001).
    2. Artzner, P., Delbaen, F., Eber, J.M., Heath, D., and
    Ku, H. Multiperiod Risk and Coherent Multi-period
    Risk Measurement, E.T.H.Zurich, Preprint (2002).
    3. Bodie, Z., Kane, A., and Marcus, A.J., Investment,
    Chicago, Irwin/McGraw-Hill, 4th Edn. (1999).
    4. Ni, E., Luh, P.B., and Rourke, S. \Optimal integrated
    generation bidding & scheduling with risk management
    under a deregulated power market", IEEE Transactions
    on Power Systems, 19, pp. 600-609 (2004).
    5. Yamin, H.Y. and Shahidehpour, S.M. \Risk and pro t
    in self-scheduling for gencos", IEEE Transactions on
    Power Systems, 19, pp. 2104-2106 (2004).
    6. Liu, M. and Wu, F.F. \Managing price risk in a multimarket
    environment", IEEE Transactions on Power
    Systems, 21, pp. 1512-1519 (2006).
    7. Jain, A.K., Srivastava, S.C., Sing, S.N., and Srivastava,
    L. \Strategic bidding in transmission constrained
    electricity markets using arti cial bee colony algorithm",
    Electric Power Components and Systems, 40,
    pp. 1768-1788 (2012).
    8. Luo, X., Chung, C., Yang, H., and Tong, X. \Optimal
    bidding strategy for generation companies under CVaR
    constraint", International Transactions on Electrical
    Energy Systems, 24, pp. 1369-1384 (2014).
    9. Garces, L.P. and Conejo, A.J. \Weekly self-scheduling,
    forward contracting, and o ering strategy for a producer",
    IEEE Transactions on Power Systems, 25, pp.
    657-666 (2010).
    10. Liu, H. and Hou, Y. \The mean-wcvar based model
    for ldc's optimal portfolio in multi-energy markets",
    International Transactions on Electrical Energy Systems,
    22, pp. 367-377 (2012)
    11. Conejo, A.J., Garca-Bertrand, R., Carrion, M., Caballero,
    A., and de Andres, A.\Optimal involvement
    in futures markets of a power producer", IEEE Transactions
    on Power Systems, 23, pp. 703-711 (2008).
    12. Xu, Z., Hu, Z., Song, Y., and Wang, J. "Risk-averse
    optimal bidding strategy for demandside resource
Scientia Iranica
Volume 25, Issue 6
Transactions on Computer Science & Engineering and Electrical Engineering (D)
November and December 2018
Pages 3475-3475

Files

Share

How to cite

Statistics