The inverse 1-maxian problem with edge length modification

被引：38

作者：

Gassner, Elisabeth ^{[1
]}

机构：

[1] Graz Univ Technol, Dept Optimizat & Discrete Math, A-8010 Graz, Austria

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2008年 / 16卷 / 01期

关键词：

obnoxious location; maxian; inverse problem; omplexity; tree;

D O I：

10.1007/s10878-007-9098-9

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We consider the problem of modifying the lengths of the edges of a graph at minimum cost such that a prespecified vertex becomes a 1-maxian with respect to the new edge lengths. The inverse 1-maxian problem with edge length modification is shown to be strongly NP-hard even on series-parallel graphs. Moreover, a transformation of the inverse 1-maxian problem with edge length modification on a tree to a minimum cost circulation problem is given which solves the original problem in O(n log n).

引用

页码：50 / 67

页数：18

共 17 条

[1] Ahuja RK, 1993, NETWORK FLOWS THEORY
[2] MINIMUM COST FLOW ALGORITHMS FOR SERIES-PARALLEL NETWORKS
BEIN, WW
BRUCKER, P
TAMIR, A
[J]. DISCRETE APPLIED MATHEMATICS, 1985, 10 (02) : 117 - 124
[3] IMPROVING THE LOCATION OF MINIMAX FACILITIES THROUGH NETWORK MODIFICATION
BERMAN, O
INGCO, DI
ODONI, A
[J]. NETWORKS, 1994, 24 (01) : 31 - 41
[4] Berman O., 1992, Annals of Operations Research, V40, P1, DOI 10.1007/BF02060467
[5] FINDING THE MINIMUM-COST MAXIMUM FLOW IN A SERIES-PARALLEL NETWORK
BOOTH, H
TARJAN, RE
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1993, 15 (03): : 416 - 446
[6] Burkard R. E., 2004, Discret. Optim, V1, P23, DOI DOI 10.1016/J.DISOPT.2004.03.003
[7] A linear time algorithm for the reverse 1-median problem on a cycle
Burkard, Rainer E.
Gassner, Elisabeth
Hatzl, Johannes
[J]. NETWORKS, 2006, 48 (01) : 16 - 23
[8] BURKARD RE, 2007, IN PRESS DISCRET APP
[9] Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[10] Goldman A. J., 1971, Transportation Science, V5, P212, DOI 10.1287/trsc.5.2.212

← 1 2 →