运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2010年
3期
31-40
,共10页
运筹学%组合最优化%图搜索%图标号%消去割宽%算法
運籌學%組閤最優化%圖搜索%圖標號%消去割寬%算法
운주학%조합최우화%도수색%도표호%소거할관%산법
Operations research%combinatorial optimization%graph labeling%graphsearching%elimination cutwidth%algorithm
图搜索问题在组合最优化学科中是一个著名的NP-完全问题.现在我们给这个问题一个限制性条件;图中的边在一次性被搜索后立即堵塞,使得这些边在以后的图搜索过程中不再被搜索.该问题起源于流行病的预防、管道的保养和维护等领域.在这个条件限制下,图搜索问题可以转化为图的消去割宽问题.本文主要研究了图的消去割宽的多项式时间算法、基本性质以及消去割宽和其它图论参数如树宽、路宽的关系,得到了一些特殊图类的消去割宽值.
圖搜索問題在組閤最優化學科中是一箇著名的NP-完全問題.現在我們給這箇問題一箇限製性條件;圖中的邊在一次性被搜索後立即堵塞,使得這些邊在以後的圖搜索過程中不再被搜索.該問題起源于流行病的預防、管道的保養和維護等領域.在這箇條件限製下,圖搜索問題可以轉化為圖的消去割寬問題.本文主要研究瞭圖的消去割寬的多項式時間算法、基本性質以及消去割寬和其它圖論參數如樹寬、路寬的關繫,得到瞭一些特殊圖類的消去割寬值.
도수색문제재조합최우화학과중시일개저명적NP-완전문제.현재아문급저개문제일개한제성조건;도중적변재일차성피수색후립즉도새,사득저사변재이후적도수색과정중불재피수색.해문제기원우류행병적예방、관도적보양화유호등영역.재저개조건한제하,도수색문제가이전화위도적소거할관문제.본문주요연구료도적소거할관적다항식시간산법、기본성질이급소거할관화기타도론삼수여수관、로관적관계,득도료일사특수도류적소거할관치.
The graph-searching problem is a well-known NP-complete problem in combinatorial optimization. Now we make a restriction on the graph-searching prob-lem 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 elim-ination 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.
