A New Subclass of Integer Linear Programming Problems and Its Applications

被引：2

作者：

Wang, Yue-Li ^{[1
]}

Hsu, Cheng-Ju ^{[2
]}

Liu, Jia-Jie ^{[3
]}

Ko, Ming-Tat ^{[4
]}

Wang, Fu-Hsing ^{[5
]}

机构：

[1] Natl Taiwan Univ Sci & Technol, Dept Informat Management, Taipei, Taiwan

[2] Ching Yun Univ, Dept Informat Management, Taipei, Taiwan

[3] Shih Hsin Univ, Dept Informat Management, Taipei, Taiwan

[4] Acad Sinica, Inst Informat Sci, Taipei, Taiwan

[5] Chinese Culture Univ, Dept Informat Management, Taipei, Taiwan

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2012年 / 61卷 / 12期

关键词：

Constrained optimization; dynamic programming; graph algorithms; integer linear programming; secure sets; trees; DEFENSIVE ALLIANCES; SECURITY; GRAPHS;

D O I：

10.1109/TC.2011.204

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we define a new subclass of integer linear programming problems called the composition problem. We shall propose efficient algorithms for solving this problem and its variants. Moreover, as an application of the composition problem, those algorithms are applied to solve the P-constrained secure set problem, which is a variation of the secure set problem introduced in [5], on trees. A P-constrained secure set problem is to find a minimum secure set containing a set of vertical bar P vertical bar predetermined vertices.

引用

页码：1813 / 1822

页数：10

共 28 条

[1]

[Anonymous], 2004, Congr. Numer.

[2]

[Anonymous], NAVAL RES LOGISTICS

[3]

[Anonymous], C NUMERANTIUM

[4]

[Anonymous], 2006, Electronic Notes in Discrete Math

[5]

[Anonymous], 1998, Theory of linear and integer programming

[6]

[Anonymous], 2003, Bulletin of the Institute of Combinatorics and its Applications

[7]

[Anonymous], 1996, Advances in Linear and Integer Programming

[8] TRAVELING SALESMAN PROBLEM - A SURVEY [J].

BELLMORE, M ;

NEHAUSE.GL .

OPERATIONS RESEARCH, 1968, 16 (03) :538-&

[9]

Blum M., 1973, Journal of Computer and System Sciences, V7, P448, DOI 10.1016/S0022-0000(73)80033-9

[10] Security in graphs [J].

Brigham, Robert C. ;

Dutton, Ronald D. ;

Hedetniemi, Stephen T. .

DISCRETE APPLIED MATHEMATICS, 2007, 155 (13) :1708-1714

← 1 2 3 →