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

Hung-Lin Fu*, C. L. Shiue, X. Cheng, D. Z. Du, J. M. Kim

*Corresponding author for this work

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

Let α be a permutation of the vertex set V(G) of a connected graph G. Define the total relative displacement of α in G by δα(G) = ∑x,y∈ V(G) |dG(x,y)-dG(α(x), α(y))|, where dG(x, y) is the length of the shortest path between x and y in G. Let π*(G) be the maximum value of δα(G) among all permutations of V(G). The permutation which realizes π*(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(n5 log n) time, where n is the total number of vertices in a complete multipartite graph.

Original languageEnglish
Pages (from-to)545-556
Number of pages12
JournalJournal of Optimization Theory and Applications
Volume110
Issue number3
DOIs
StatePublished - 1 Sep 2001

Keywords

  • Chaotic mapping
  • Complete multipartite graph
  • Optimal solution
  • Quadratic integer programming

Fingerprint Dive into the research topics of 'Quadratic integer programming with application to the chaotic mappings of complete multipartite graphs'. Together they form a unique fingerprint.

  • Cite this