標題: 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
顯示於類別:期刊論文


文件中的檔案:

  1. 000171212900004.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。