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.
Fu, Hung-Lin; Shiue, Chin-lin; Cheng, Xiuzhen; Du, Ding-Zhu; Kim, Joon-Mo.
A Quadratic Integer Programming with Application in Chaotic Mappings of Complete Multipartite Graphs.
Retrieved from the University of Minnesota Digital Conservancy,
Content distributed via the University of Minnesota's Digital Conservancy may be subject to additional license and use restrictions applied by the depositor.