Quadratic integer programming with application to the chaotic mappings of complete multipartite graphs

被引：10

作者：

Fu, HL ^{[1
]}

Shiue, CL

Cheng, X

Du, DZ

Kim, JM

机构：

[1] Natl Chiao Thung Univ, Dept Appl Math, Hsinchu, Taiwan

[2] Natl Tsing Hua Univ, Natl Ctr Theoret Sci, Div Math, Hsinchu, Taiwan

[3] Univ Minnesota, Dept Comp Sci & Engn, Minneapolis, MN USA

[4] Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China

来源：

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS | 2001年 / 110卷 / 03期

关键词：

chaotic mapping; complete multipartite graph; quadratic integer programming; optimal solution;

D O I：

10.1023/A:1017584227417

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：545 / 556

页数：12

共 6 条

[1] Total relative displacement of permutations [J].