E-viri
Recenzirano
-
Zhang, Qiao; Guan, Xiucui; Jia, Junhua; Qian, Xinqiang; Pardalos, Panos M
Journal of global optimization, 05/2023, Letnik: 86, Številka: 1Journal Article
We consider the restricted inverse optimal value problem on shortest path under weighted Formula omitted norm on trees (RIOVSPT Formula omitted). It aims at adjusting some edge weights to minimize the total cost under weighted Formula omitted norm on the premise that the length of the shortest root-leaf path of the tree is lower-bounded by a given value D, which is just the restriction on the length of a given root-leaf path Formula omitted. If we ignore the restriction on the path Formula omitted, then we obtain the minimum cost shortest path interdiction problem on trees (MCSPIT Formula omitted). We analyze some properties of the problem (RIOVSPT Formula omitted) and explore the relationship of the optimal solutions between (MCSPIT Formula omitted) and (RIOVSPT Formula omitted). We first take the optimal solution of the problem (MCSPIT Formula omitted) as an initial infeasible solution of problem (RIOVSPT Formula omitted). Then we consider a slack problem Formula omitted, where the length of the path Formula omitted is greater than D. We obtain its feasible solutions gradually approaching to an optimal solution of the problem (RIOVSPT Formula omitted) by solving a series of subproblems Formula omitted. It aims at determining the only weight-decreasing edge on the path Formula omitted with the minimum cost so that the length of the shortest root-leaf path is no less than D. The subproblem can be solved by searching for a minimum cost cut in O(n) time. The iterations continue until the length of the path Formula omitted equals D. Consequently, the time complexity of the algorithm is Formula omitted and we present some numerical experiments to show the efficiency of the algorithm. Additionally, we devise a linear time algorithm for the problem (RIOVSPT Formula omitted) under unit Formula omitted norm.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.