DocumentCode
1361111
Title
A New Subclass of Integer Linear Programming Problems and Its Applications
Author
Wang, Yue-Li ; Hsu, Cheng-Ju ; Liu, Jia-Jie ; Ko, Ming-Tat ; Wang, Fu-Hsing
Author_Institution
Dept. of Inf. Manage., Nat. Taiwan Univ. of Sci. & Technol., Taipei, Taiwan
Volume
61
Issue
12
fYear
2012
Firstpage
1813
Lastpage
1822
Abstract
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 |P| predetermined vertices.
Keywords
integer programming; linear programming; set theory; trees (mathematics); P-constrained secure set problem; composition problem; integer linear programming; predetermined vertices; trees; Dynamic programming; Electronic mail; Energy efficiency; Energy management; Graphical models; Integer linear programming; Linear programming; Optimization; Constrained optimization; dynamic programming; graph algorithms; integer linear programming; secure sets; trees;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/TC.2011.204
Filename
6060797
Link To Document