ON AN INSTANCE OF THE INVERSE SHORTEST PATHS PROBLEM

被引：259

作者：

BURTON, D

TOINT, PL

机构：

[1] Belgian National Fund for Scientific Research, Department of Mathematics, Facultés Universitaires ND de la Paix, Namur

来源：

MATHEMATICAL PROGRAMMING | 1992年 / 53卷 / 01期

关键词：

GRAPH THEORY; SHORTEST PATHS; INVERSE PROBLEMS; QUADRATIC PROGRAMMING;

D O I：

10.1007/BF01585693

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The inverse shortest paths problem in a graph is considered, that is, the problem of recovering the arc costs given some information about the shortest paths in the graph. The problem is first motivated by some practical examples arising from applications. An algorithm based on the Goldfarb-Idnani method for convex quadratic programming is then proposed and analyzed for one of the instances of the problem. Preliminary numerical results are reported.

引用

页码：45 / 61

页数：17

共 15 条

[1] A PROJECTED NEWTON METHOD FOR 1P NORM LOCATION-PROBLEMS [J].

CALAMAI, PH ;

CONN, AR .

MATHEMATICAL PROGRAMMING, 1987, 38 (01) :75-109

[2]

CALAMAI PH, 1982, LECT NOTES MATH, V912, P1

[3]

CALAMAI PH, 1980, SIAM J SCI STAT COMP, V4, P512

[4]

Dijkstra E.W., 1959, NUMER MATH, V1, P269, DOI [DOI 10.1007/BF01386390, 10.1007/BF01386390]

[5]

GEORGE A, 1981, COMPUTER SOLUTION LA

[6] A NUMERICALLY STABLE DUAL METHOD FOR SOLVING STRICTLY CONVEX QUADRATIC PROGRAMS [J].

GOLDFARB, D ;

IDNANI, A .

MATHEMATICAL PROGRAMMING, 1983, 27 (01) :1-33

[7]

Golub G.H., 2013, MATRIX COMPUTATIONS

[8] EFFICIENT ALGORITHMS FOR SHORTEST PATHS IN SPARSE NETWORKS [J].

JOHNSON, DB .

JOURNAL OF THE ACM, 1977, 24 (01) :1-13

[9] INVERSION OF SEISMIC DATA USING TOMOGRAPHIC RECONSTRUCTION TECHNIQUES FOR INVESTIGATIONS OF LATERALLY INHOMOGENEOUS-MEDIA [J].

NEUMANNDENZAU, G ;

BEHRENS, J .

GEOPHYSICAL JOURNAL OF THE ROYAL ASTRONOMICAL SOCIETY, 1984, 79 (01) :305-315

[10]

Nolet G., 1987, SEISMIC TOMOGRAPHY

← 1 2 →