| TWO FEEDBACK PROBLEMS FOR GRAPHS WITH BOUNDED TREE-WIDTH |
| |
| 作者姓名： | ZhangShaoqiang LiGuojun SohnMoo-Young |
| |
| 作者单位： | [1]SchoolofMathematicsandSystemsScience.ShandongUniversity,Jinan250100,China [2]InstituteofSoftware,ChineseAcademyofSciences.Beijing100080,China [3]Dept.ofAppl.Math.,ChangwonNationalUniv.,Changwon641-773,Korea |
| |
| 基金项目： | Partially supported by the National Natural Science Foundation of China( 1 0 2 71 0 65 |
| |
| 摘 要： | Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree decomposition. In this paper,it is discussed how to solve the minimum feedback vertex set problem and the minimum vertex feedback edge set problem efficiently by using dynamic programming on a tree-decomposition.
|
| 关 键 词： | 最优化问题 图表 树 分解 动力学 |
| 收稿时间： | 29 May 2003 |
Two feedback problems for graphs with bounded tree-width |
| |
| ZhangShaoqiang LiGuojun SohnMoo-Young.TWO FEEDBACK PROBLEMS FOR GRAPHS WITH BOUNDED TREE-WIDTH[J].Applied Mathematics A Journal of Chinese Universities,2004,19(2):149-154. |
| |
| Authors: | Zhang Shaoqiang Li Guojun Sohn Moo-Young |
| |
| Institution: | (1) School of Mathematics and Systems Science, Shandong University, 250100 Jinan, China;(2) Mathematics Department, Tianjin Normal University, 300074 Tianjin, China;(3) Institute of Software, Chinese Academy of Sciences, 100080 Beijing, China;(4) Dept. of Appl. Math., Changwon National Univ., 641-773 Changwon, Korea |
| |
| Abstract: | Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex set problem and the minimum vertex feedback edge set problem efficiently by using dynamic programming on a tree-decomposition. |
| |
| Keywords: | feedback vertex set feedback edge set tree-decomposition tree-width dynamic programming |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
