Presentation	2001/9/7 Linear Layouts of Multidimensional Torus Graphs Shuji JIMBO, Kosaburo HASHIGUCHI, Hitoshi MUTO,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	A linear layout L of a graph G is a one-to-one mapping from the vertex-set of G onto {1, 2, …, |V(G)|}. the value Σ_|L(v)-L(w)| is called the sum of edge length of L. For a pair of positive integers n and m, the n-dimensional m-torus graph T^n_m is an undirected graph whose vertex-set and edge-set are the set of all 〓_m-valued n-dimensional vectors and the set of all edges that join two vertices such that the norm of the difference between them is just 1. The natural layout of T^n_m is the linear layout that regards a vertex as a m-adic number and arranges the vertices in acending order. In this report, it is proved that, for every positive integer n, the sum of edge length of the natural layout is the minimum among the ones of all linear layouts of T^n_3. Furthermore, the set of linear layouts of T^n_3 whose sum of edge length is the maximum is completely characterized.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	graph theory / hypercube / torus / linear layout / sum of edge length / optimization problem
Paper #	COMP2001-32
Date of Issue

Conference Information
Committee	COMP
Conference Date	2001/9/7(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Linear Layouts of Multidimensional Torus Graphs
Sub Title (in English)
Keyword(1)	graph theory
Keyword(2)	hypercube
Keyword(3)	torus
Keyword(4)	linear layout
Keyword(5)	sum of edge length
Keyword(6)	optimization problem
1st Author's Name	Shuji JIMBO
1st Author's Affiliation	Faculty of Engineering, Okayama University()
2nd Author's Name	Kosaburo HASHIGUCHI
2nd Author's Affiliation	Faculty of Engineering, Okayama University
3rd Author's Name	Hitoshi MUTO
3rd Author's Affiliation	MEITEC CORPORATION
Date	2001/9/7
Paper #	COMP2001-32
Volume (vol)	vol.101
Number (no)	307
Page	pp.pp.-
#Pages	8
Date of Issue