| TWO FEEDBACK PROBLEMS FOR GRAPHS WITH BOUNDED TREE-WIDTH |
| |
| 引用本文： | ZhangShaoqiang LiGuojun SohnMoo-Young. TWO FEEDBACK PROBLEMS FOR GRAPHS WITH BOUNDED TREE-WIDTH[J]. 高校应用数学学报(英文版), 2004, 19(2): 149-154. DOI: 10.1007/s11766-004-0048-3 |
| |
| 作者姓名： | 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.
|
| 关 键 词： | 最优化问题 图表 树 分解 动力学 |
| 收稿时间： | 2003-05-29 |
Two feedback problems for graphs with bounded tree-width |
| |
| Zhang Shaoqiang,Li Guojun,Sohn Moo-Young. Two feedback problems for graphs with bounded tree-width[J]. Applied Mathematics A Journal of Chinese Universities, 2004, 19(2): 149-154. DOI: 10.1007/s11766-004-0048-3 |
| |
| Authors: | Zhang Shaoqiang Li Guojun Sohn Moo-Young |
| |
| Affiliation: | (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 等数据库收录！ |
