图的消去割宽问题(英文)  

The Elimination Cutwidth Problem for Graphs

作　　者：张振坤[1] 高风昕[1] 

机构地区：[1]黄淮学院数学系,驻马店463000

出　　处：《运筹学学报》2010年第3期31-40,共10页Operations Research Transactions

基　　金：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 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.

关 键 词：运筹学 组合最优化 图搜索 图标号 消去割宽 算法 

分 类 号：O157.5[理学—数学]