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 [J].

BEIN, WW ;

BRUCKER, P ;

TAMIR, A .

DISCRETE APPLIED MATHEMATICS, 1985, 10 (02) :117-124

[3] IMPROVING THE LOCATION OF MINIMAX FACILITIES THROUGH NETWORK MODIFICATION [J].

BERMAN, O ;

INGCO, DI ;

ODONI, A .

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 [J].

BOOTH, H ;

TARJAN, RE .

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 [J].

Burkard, Rainer E. ;

Gassner, Elisabeth ;

Hatzl, Johannes .

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 →