|
%I #18 May 28 2021 18:47:52
%S 0,6,24,60,116,200,318,472,668,914,1214,1568,1988,2480,3040,3680,4408,
%T 5224,6130,7140,8260,9478,10816,12280,13864,15576,17430,19428,21560,
%U 23850,26304,28908,31680,34632,37760,41060,44556,48254,52130,56216,60520,65030
%N a(n) is the optimal wire-length for an n X n grid.
%C This problem is also known as the linear arrangement problem or the wire-length 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 NP-hard, but exact solutions are known for rectangular grids. This sequence corresponds to optimal solutions for n X n square grids.
%D T. Y. Berger-Wolf, Wirelength of a Grid Graph, 2001.
%D P. Fishburn and P. Tetali and P. Winkler, Optimal linear arrangement of a rectangular grid, Discrete Mathematics, 2000, pages 123-139.
%D D. O. Muradyan and T. E. Piliposjan, Minimal Numberings of Vertices of a Rectangular Lattice, Akad. Nauk. Armjan. SSR. Dokl. 70, 1980, pages 21-27 (in Russian).
%F 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).
%e For n=2 an optimal grid arrangement is
%e 1 2
%e 4 3
%e The value of this arrangement is |1-2| + |1-4| + |2-3| + |3-4|=6.
%e For n=8 an optimal grid looks like so:
%e 64 63 60 40 25 07 02 01
%e 62 61 59 39 26 08 04 03
%e 58 57 56 38 27 09 06 05
%e 55 54 53 37 28 12 11 10
%e 52 51 50 36 29 15 14 13
%e 49 48 43 35 30 18 17 16
%e 47 46 42 34 31 23 20 19
%e 45 44 41 33 32 24 22 21
%K nonn
%O 1,2
%A _Dmitry Kamenetsky_, Sep 21 2011
|
