|
|||||
|
|
Complexity of domination,hamiltonicity and treewidth for tree convex bipartite graphs |
|
| Authors: | Hao Chen Zihan Lei Tian Liu Ziyang Tang Chaoyi Wang Ke Xu |
| Institution: | 1. College of Information Engineering, Shijiazhuang University of Economics, Shijiazhuang?, 050031, China 2. College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang?, 050024, China 3. Laboratory of Network and Information Security, Shijiazhuang University of Economics, Shijiazhuang?, 050031, China 4. Department of Industrial and System Engineering, University of Florida, Gainesville, FL?, 32611, USA 5. Department of Computer Science, University of Texas at Dallas, Richardson, TX?, 75080, USA |
| Abstract: | In this paper, we first give the definition of randomized time-varying knapsack problems (\(\textit{RTVKP}\)) and its mathematic model, and analyze the character about the various forms of \(\textit{RTVKP}\). Next, we propose three algorithms for \(\textit{RTVKP}\): (1) an exact algorithm with pseudo-polynomial time based on dynamic programming; (2) a 2-approximation algorithm for \(\textit{RTVKP}\) based on greedy algorithm; (3) a heuristic algorithm by using elitists model based on genetic algorithms. Finally, we advance an evaluation criterion for the algorithm which is used for solving dynamic combinational optimization problems, and analyze the virtue and shortage of three algorithms above by using the criterion. For the given three instances of \(\textit{RTVKP}\), the simulation computation results coincide with the theory analysis. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |