THE KAPPA MOST VITAL ARCS IN THE SHORTEST-PATH PROBLEM

作     者：MALIK, K MITTAL, AK GUPTA, SK 

作者机构：INDIAN INST TECHNOLKANPUR 208016UTTAR PRADESHINDIA 

出 版 物：《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期：1989年第8卷第4期

页      面：223-227页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：networks distance algorithm vital arcs shortest paths 

摘      要：The k most vital arcs in a network are those whose removal from the network results in the greatest increase in the shortest distance between two specified nodes. An exact algorithm is proposed to determine the k most vital arcs. Furthermore, an algorithm of time complexity equal to that of Dijkstra s algorithm for the shortest path problem is developed to solve the single most vital arc problem.