Return to search

著色數的規畫模型及應用

著色問題(graph coloring problem)的研究已行之有年,並衍生出廣泛的實際應用,但還缺乏一般化的著色問題模型。本論文建構一般化的著色問題模型,其目標函數包含顏色成本的固定支出和點著色變動成本。此著色模型為0/1整數線性規畫模型,其限制式含有選點問題(node packing problem)的限制式。我們利用圖中的極大團(maximal clique)所構成的強力限制式,取代原有的選點限制式,縮短求解時間。我們更進一步舉出一個特殊指派問題並將此著色模型應用於此指派問題上。本論文亦針對此指派問題發展了一個演算法來尋找極大團。計算結果顯示極大團限制式對於此著色問題模型的求解有極大的效益。 / The graph coloring problem (GCP) has been studied for a long time and it has a wide variety of applications. A straightforward formulation of graph coloring problem has not been formulated yet. In this paper, we formulate a general GCP model that concerns setup cost and variable cost of different colors. The resulting model is an integer program that involves the packing constraint. The packing constraint in the GCP model can be replaced by the maximal clique constraint in order to shorten the solution time. A special assignment problem is presented which essentially is a GCP model application. An algorithm of finding maximal cliques for this assignment problem is developed. The computational results show the efficiency of maximal clique constraints for the GCP problem.

Identiferoai:union.ndltd.org:CHENGCHI/A2010000326
Creators王竣玄
Publisher國立政治大學
Source SetsNational Chengchi University Libraries
Language中文
Detected LanguageEnglish
Typetext
RightsCopyright © nccu library on behalf of the copyright holders

Page generated in 0.002 seconds