Title
A Quadratic Integer Programming with Application in Chaotic Mappings of Complete Multipartite Graphs
Abstract
Let alpha be a permutation of V(G) of a connected graph G. Define the total relative displacement of alpha in G by
where dG(x,y) is the length of the shortest path between x and y in G. Let pi*(G) be the maximum value of deltaalpha(G) among all permutations of V(G) and 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 will reduce to a quadratic integer programming. We characterize its optimal solution and present an algorithm running in O(n5log n) time where n is the total number of vertices in a complete multipartite graph.
Suggested Citation
Fu, Hung-Lin; Shiue, Chin-lin; Cheng, Xiuzhen; Du, Ding-Zhu; Kim, Joon-Mo.
(2000).
A Quadratic Integer Programming with Application in Chaotic Mappings of Complete Multipartite Graphs.
Retrieved from the University of Minnesota Digital Conservancy,
https://hdl.handle.net/11299/215439.