On the complexity of the robust spanning tree problem with interval data

被引：44

作者：

Aron, ID ^{[1
]}

Van Hentenryck, P ^{[1
]}

机构：

[1] Brown Univ, Dept Comp Sci, Providence, RI 02912 USA

来源：

OPERATIONS RESEARCH LETTERS | 2004年 / 32卷 / 01期

关键词：

robust spanning tree; robust optimization; uncertainty; interval data;

D O I：

10.1016/S0167-6377(03)00058-0

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper studies the complexity of the robust spanning tree problem with interval data (RSTID). It shows that the problem is NP-complete, settling the conjecture of Kouvelis and Yu, and that it remains so for complete graphs or when the intervals are all [0, 1]. These results indicate that the difficulty of RSTID stems from both the graph topology and the structure of the cost intervals, suggesting new directions for search algorithms. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：36 / 40

页数：5

共 20 条

[1] INVARIANCE PROPERTIES OF CENTRAL TREES [J].

AMOIA, V ;

COTTAFAV.G .

IEEE TRANSACTIONS ON CIRCUIT THEORY, 1971, CT18 (04) :465-&

[2]

ARON I, 2002, P 18 C UAI EDM CAN A

[3]

BERTSIMAS D, 2002, ROBUST DISCRETS OPTI

[4]

BEZRUKOV S, 1996, LECT NOTES COMPUTER, V1120, P53

[5] A CENTRAL TREE [J].

DEO, N .

IEEE TRANSACTIONS ON CIRCUIT THEORY, 1966, CT13 (04) :439-&

[6] ON TREES OF A GRAPH AND THEIR GENERATION [J].

HAKIMI, SL .

JOURNAL OF THE FRANKLIN INSTITUTE-ENGINEERING AND APPLIED MATHEMATICS, 1961, 272 (05) :347-&

[7]

KADERALI F, 1973, 19 FB

[8] MAXIMALLY DISTANT TREES AND PRINCIPAL PARTITION OF A LINEAR GRAPH [J].

KISHI, G ;

KAJITANI, Y .

IEEE TRANSACTIONS ON CIRCUIT THEORY, 1969, CT16 (03) :323-&

[9]

Kouvelis P., 1997, ROBUST DISCRETE OPTI

[10]

Kozina G., 1994, INTERVAL COMPUTATION, V1, P42

← 1 2 →