login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A195647 a(n) is the optimal wire-length 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 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.

REFERENCES

T. Y. Berger-Wolf, 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 123-139.

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).

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 |1-2|+|1-4|+|2-3|+|3-4|=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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 22 05:54 EST 2020. Contains 332116 sequences. (Running on oeis4.)