Weighted inverse minimum spanning tree problems under Hamming distance

被引：56

作者：

He, Y ^{[1
]}

Zhang, BW ^{[1
]}

Yao, EY ^{[1
]}

机构：

[1] Zhejiang Univ, Dept Math, State Key Lab CAD & CG, Hangzhou 310027, Peoples R China

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2005年 / 9卷 / 01期

基金：

中国国家自然科学基金;

关键词：

minimum spanning tree; inverse problem; strongly polynomial algorithm;

D O I：

10.1007/s10878-005-5486-1

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper, we consider weighted inverse minimum spanning tree problems under Hamming distance. Three models are considered: unbounded case, unbounded case with forbidden edges, and general bounded case. In terms of the method for minimum-weight node cover problem on bipartite graph, we present their respective strongly polynomial algorithms.

引用

页码：91 / 100

页数：10

共 11 条

[1] A faster algorithm for the inverse spanning tree problem [J].

Ahuja, RK ;

Orlin, JB .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2000, 34 (01) :177-193

[2]

Ahuja RK, 1993, NETWORK FLOWS THEORY

[3] Inverse combinatorial optimization: A survey on problems, methods, and results [J].

Heuberger, C .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2004, 8 (03) :329-361

[4]

Lawler E., 1976, Combinatorial Optimization: Networks and Matroids

[5]

LI BY, 2000, THESIS ZHEJIANG U HA

[6]

MOTWANI R, 2000, LECT NOTES STANFORD

[7] Solving inverse spanning tree problems through network flow techniques [J].

Sokkalingam, PT ;

Ahuja, RK ;

Orlin, JB .

OPERATIONS RESEARCH, 1999, 47 (02) :291-298

[8]

ZHANG J, 1996, MATH METHOD OPER RES, V44, P171

[9] An algorithm for inverse minimum spanning tree problem [J].

Zhang, JH ;

Xu, SJ ;

Ma, ZF .

OPTIMIZATION METHODS & SOFTWARE, 1997, 8 (01) :69-84

[10] A general model of some inverse combinatorial optimization problems and its solution method under l∞ norm [J].

Zhang, JZ ;

Liu, ZH .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2002, 6 (02) :207-227

← 1 2 →