

A195647


a(n) is the optimal wirelength for a 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

Table of n, a(n) for n=1..42.


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

Sequence in context: A201598 A329858 A211615 * A086768 A160944 A160936
Adjacent sequences: A195644 A195645 A195646 * A195648 A195649 A195650


KEYWORD

nonn


AUTHOR

Dmitry Kamenetsky, Sep 21 2011


STATUS

approved



