| 图的消去割宽问题 |
| |
| 引用本文： | 张振坤,高风昕.图的消去割宽问题[J].运筹学学报,2010,14(3):32-40. |
| |
| 作者姓名： | 张振坤 高风昕 |
| |
| 作者单位： | 黄淮学院数学系,驻马店,463000 |
| |
| 基金项目： | The project is supported by the Natural Science Foundation of Henan Province(No.082300460190); the Program for Science and Technology Innovation Talents in Universities of Henan Province(No. 2010HASTIT043) |
| |
| 摘 要： | 图搜索问题在组合最优化学科中是一个著名的NP-完全问题.现在我们给这个问题一个限制性条件：图中的边在一次性被搜索后立即堵塞，使得这些边在以后的图搜索过程中不再被搜索.该问题起源于流行病的预防、管道的保养和维护等领域. 在这个条件限制下，图搜索问题可以转化为图的消去割宽问题.本文主要研究了图的消去割宽的多项式时间算法、基本性质以及消去割宽和其它图论参数如树宽、路宽的关系，得到了一些特殊图类的消去割宽值.
|
| 关 键 词： | 运筹学 组合最优化 图搜索 图标号 消去割宽 算法 |
The Elimination Cutwidth Problem for Graphs |
| |
| Zhang Zhenkun,Gao Fengxin.The Elimination Cutwidth Problem for Graphs[J].OR Transactions,2010,14(3):32-40. |
| |
| Authors: | Zhang Zhenkun Gao Fengxin |
| |
| Affiliation: | Zhang Zhenkun Gao Fengxin 1.Department of Mathematics,Huanghuai University,Zhumadian 463000,China |
| |
| Abstract: | The graph-searching problem is a well-known $NP-$complete problem in combinatorial optimization. Now we make a restriction on the graph-searching problem that an edge is closed as soon as it is searched and need not be searched again. The problem arises from epidemic prevention, the maintenance and repairing of pipeline networks, etc. This restrictive graph-searching problem can be transformed into the elimination cutwidth problem for graphs. In this paper, a polynomial-time algorithm and some fundamental properties of elimination cutwidth $EC(G)$ are mainly presented. Also, the relations with other parameters (such as treewidth and pathwidth) and some special graph results are discussed. |
| |
| Keywords: | Operations research combinatorial optimization graph labeling graphsearching elimination cutwidth algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载全文 |
