

A195647


a(n) is the optimal wirelength for an n X n grid.


0



0, 6, 24, 60, 116, 200, 318, 472, 668, 914, 1214, 1568, 1988, 2480, 3040, 3680, 4408, 5224, 6130, 7140, 8260, 9478, 10816, 12280, 13864, 15576, 17430, 19428, 21560, 23850, 26304, 28908, 31680, 34632, 37760, 41060, 44556, 48254, 52130, 56216, 60520, 65030
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

This problem is also known as the linear arrangement problem or the wirelength problem. The task is to label the vertices of a graph with distinct positive integers such that the sum of label differences over all the edges is minimal. More formally, given a finite simple graph G=(V,E) with vertex set V and edge set E, we need to find a map f from V onto {1,2, ..., V} that minimizes the sum f(u)  f(v) over all edges (u,v) in E. In general this problem is NPhard, but exact solutions are known for rectangular grids. This sequence corresponds to optimal solutions for n X n square grids.


REFERENCES

T. Y. BergerWolf, Wirelength of a Grid Graph, 2001.
P. Fishburn and P. Tetali and P. Winkler, Optimal linear arrangement of a rectangular grid, Discrete Mathematics, 2000, pages 123139.
D. O. Muradyan and T. E. Piliposjan, Minimal Numberings of Vertices of a Rectangular Lattice, Akad. Nauk. Armjan. SSR. Dokl. 70, 1980, pages 2127 (in Russian).


LINKS



FORMULA

a(n) = n*(n^2 + n  2)  t*(2t^2  6nt + 3n^2 + 3n  2)/3, where t = round((6n  sqrt(6*(2  3n + 3n^2)))/6).


EXAMPLE

For n=2 an optimal grid arrangement is
1 2
4 3
The value of this arrangement is 12 + 14 + 23 + 34=6.
For n=8 an optimal grid looks like so:
64 63 60 40 25 07 02 01
62 61 59 39 26 08 04 03
58 57 56 38 27 09 06 05
55 54 53 37 28 12 11 10
52 51 50 36 29 15 14 13
49 48 43 35 30 18 17 16
47 46 42 34 31 23 20 19
45 44 41 33 32 24 22 21


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



