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

H. L. Fu; C. L. Shiue; X. Cheng; D. Z. Du; J. M. Kim

doi:10.1023/A:1017584227417

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

H. L. Fu, C. L. Shiue, X. Cheng, D. Z. Du, J. M. Kim

Research output: Contribution to journal › Article › peer-review

11 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) |d_G(x,y)-d_G(α(x), α(y))|, where d_G(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(n⁵ log n) time, where n is the total number of vertices in a complete multipartite graph.

Original language	English (US)
Pages (from-to)	545-556
Number of pages	12
Journal	Journal of Optimization Theory and Applications
Volume	110
Issue number	3
DOIs	https://doi.org/10.1023/A:1017584227417
State	Published - Sep 2001
Externally published	Yes

All Science Journal Classification (ASJC) codes

Control and Optimization
Management Science and Operations Research
Applied Mathematics

Keywords

Chaotic mapping
Complete multipartite graph
Optimal solution
Quadratic integer programming

Access to Document

10.1023/A:1017584227417

Cite this

@article{b66eb710c48b4738b73d7d9bb38b1de9,

title = "Quadratic integer programming with application to the chaotic mappings of complete multipartite graphs",

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.",

keywords = "Chaotic mapping, Complete multipartite graph, Optimal solution, Quadratic integer programming",

author = "Fu, {H. L.} and Shiue, {C. L.} and X. Cheng and Du, {D. Z.} and Kim, {J. M.}",

note = "Funding Information: 1This paper was supported by ROC Grant NSC-89-2115-M-009-019, ROC Grant NSC-89-2119-M-009-002, and PRC Program 973 on Information Technology and High-Performance Software. 2This work was motivated by the work of Ref. 1 and a personal communication with Dr. K. B. Reid. We wish to thank him for his references and encouragement. 3Professor, Department of Applied Mathematics, National Chiao Thung University, Hsin Chu, Taiwan. 4Professor, Mathematics Division, National Center for Theoretical Science, National Tsing Hua University, Hsin Chu, Taiwan. 5Graduate Student, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, Minnesota. 6Professor, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, Minnesota. 7Professor, Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing, PRC.",

year = "2001",

month = sep,

doi = "10.1023/A:1017584227417",

language = "English (US)",

volume = "110",

pages = "545--556",

journal = "Journal of Optimization Theory and Applications",

issn = "0022-3239",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

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

AU - Fu, H. L.

AU - Shiue, C. L.

AU - Cheng, X.

AU - Du, D. Z.

AU - Kim, J. M.

N1 - Funding Information: 1This paper was supported by ROC Grant NSC-89-2115-M-009-019, ROC Grant NSC-89-2119-M-009-002, and PRC Program 973 on Information Technology and High-Performance Software. 2This work was motivated by the work of Ref. 1 and a personal communication with Dr. K. B. Reid. We wish to thank him for his references and encouragement. 3Professor, Department of Applied Mathematics, National Chiao Thung University, Hsin Chu, Taiwan. 4Professor, Mathematics Division, National Center for Theoretical Science, National Tsing Hua University, Hsin Chu, Taiwan. 5Graduate Student, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, Minnesota. 6Professor, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, Minnesota. 7Professor, Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing, PRC.

PY - 2001/9

Y1 - 2001/9

N2 - 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.

AB - 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.

KW - Chaotic mapping

KW - Complete multipartite graph

KW - Optimal solution

KW - Quadratic integer programming

UR - http://www.scopus.com/inward/record.url?scp=0035219288&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035219288&partnerID=8YFLogxK

U2 - 10.1023/A:1017584227417

DO - 10.1023/A:1017584227417

M3 - Article

AN - SCOPUS:0035219288

SN - 0022-3239

VL - 110

SP - 545

EP - 556

JO - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

IS - 3

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this