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

CSpace

	Quadratic integer programming with application to the chaotic mappings of complete multipartite graphs
	Fu, HL ; Shiue, CL ; Cheng, X ; Du, DZ ; Kim, JM
	2001-09-01
发表期刊	JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
ISSN	0022-3239
卷号	110 期号:3 页码:545-556
摘要	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.
关键词	chaotic mapping complete multipartite graph quadratic integer programming optimal solution
语种	英语
WOS研究方向	Operations Research & Management Science ; Mathematics
WOS类目	Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000171212900004
出版者	KLUWER ACADEMIC/PLENUM PUBL
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/15857
专题	中国科学院数学与系统科学研究院
通讯作者	Fu, HL
作者单位	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
推荐引用方式 GB/T 7714	Fu, HL,Shiue, CL,Cheng, X,et al. Quadratic integer programming with application to the chaotic mappings of complete multipartite graphs[J]. JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS,2001,110(3):545-556.
APA	Fu, HL,Shiue, CL,Cheng, X,Du, DZ,&Kim, JM.(2001).Quadratic integer programming with application to the chaotic mappings of complete multipartite graphs.JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS,110(3),545-556.
MLA	Fu, HL,et al."Quadratic integer programming with application to the chaotic mappings of complete multipartite graphs".JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 110.3(2001):545-556.