The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A195647 a(n) is the optimal wire-length 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 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 11 08:31 EST 2023. Contains 367717 sequences. (Running on oeis4.)