Title: Vertex Coloring Model and Algorithm of Gate Assignment
Abstract: Vertex coloring model and decomposing algorithm of gate assignment problem is offered.By improving an algorithm of time conflict,the set of the time conflict of the scheduled flights is constructed.Based on the in first out principle,gate assignment problem is transferred to vertex-coloring problem,and corresponding model is constructed also.By utilizing authors' innovative decompose algorithm,it is possible to improve gates' operation ability and the algorithm's computational complexity is O(n2).The algorithm's characteristic is that 1) it divides vertices and colors into different levels' sets,and 2) vertices are decomposed according to the set level that they belong to and their degrees,then every vertex's decompose sequence number(VDSN) is obtained.When assign color ck(1≤k≤K;K is the colors number that can be used) to a vertex, assign color ck to such a vertex that the vertex can be assigned color ck and its VDSN is the biggest.Finally,an example is offered to demonstrate the application of the algorithm and the optimal solution is obtained.
Publication Year: 2007
Publication Date: 2007-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot