標題: | Quadratic integer programming with application to the chaotic mappings of complete multipartite graphs |
作者: | Fu, HL Shiue, CL Cheng, X Du, DZ Kim, JM 應用數學系 Department of Applied Mathematics |
關鍵字: | chaotic mapping;complete multipartite graph;quadratic integer programming;optimal solution |
公開日期: | 1-九月-2001 |
摘要: | Let a be a permutation of the vertex set V(G) of a connected graph G. Define the total relative displacement of alpha in G by [GRAPHIC] where d(G) (x, y) is the length of the shortest path between x and y in G. Let pi*(G) be the maximum value of delta (alpha)(G) among all permutations of V(G). The permutation which realizes pi*(G) is called a chaotic mapping of G. In this paper, we study the chaotic mappings of complete multipartite graphs. The problem is reduced to a quadratic integer programming problem. We characterize its optimal solution and present an algorithm running in O(n(5) log n) time, where n is the total number of vertices in a complete multipartite graph. |
URI: | http://dx.doi.org/10.1023/A:1017584227417 http://hdl.handle.net/11536/29429 |
ISSN: | 0022-3239 |
DOI: | 10.1023/A:1017584227417 |
期刊: | JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS |
Volume: | 110 |
Issue: | 3 |
起始頁: | 545 |
結束頁: | 556 |
顯示於類別: | 期刊論文 |