M-spline

2013-03-16T22:52:24Z

95.209.155.37: minor

: ''This article is about the heuristic algorithm for the graph partitioning problem. For a heuristic for the traveling salesperson problem, see [[Lin–Kernighan heuristic]].''
'''Kernighan–Lin''' is a O(n<sup>3</sup> ) [[heuristic algorithm]] for solving the [[graph partitioning problem]]. The algorithm has important applications in the layout of digital circuits and components in [[VLSI]].<ref name="kl"/><ref name="ravikumar"/>

==Description==
Let <math>G(V,E)</math> be a graph, and let <math>V</math> be the set of nodes and <math>E</math> the set of edges. The algorithm attempts to find a partition of <math>V</math> into two disjoint subsets <math>A</math> and <math>B</math> of equal size, such that the sum <math>T</math> of the weights of the edges between nodes in <math>A</math> and <math>B</math> is minimized. Let <math>I_{a}</math> be the ''internal cost'' of ''a'', that is, the sum of the costs of edges between ''a'' and other nodes in ''A'', and let <math>E_{a}</math> be the ''external cost'' of ''a'', that is, the sum of the costs of edges between ''a'' and nodes in ''B''. Furthermore, let
:<math>D_{a} = E_{a} - I_{a}</math>
be the difference between the external and internal costs of ''a''. If ''a'' and ''b'' are interchanged, then the reduction in cost is
:<math>T_{old} - T_{new} = D_{a} + D_{b} - 2c_{a,b}</math>
where <math>c_{a,b}</math> is the cost of the possible edge between ''a'' and ''b''.

The algorithm attempts to find an optimal series of interchange operations between elements of <math>A</math> and <math>B</math> which maximizes <math>T_{old} - T_{new}</math> and then executes the operations, producing a partition of the graph to ''A'' and ''B''.<ref name="kl">{{cite journal|first1=B. W.|last1=Kernighan|authorlink1=Brian Kernighan|first2=Shen|last2=Lin|authorlink2=Shen Lin| year = 1970 | title = An efficient heuristic procedure for partitioning graphs | journal = Bell Systems Technical Journal|volume=49|pages=291–307}}</ref>

==Pseudocode==
See <ref name="ravikumar">{{cite book|last=Ravikumār|first=Si. Pi|coauthors=Ravikumar, C.P|title=Parallel methods for VLSI layout design|publisher=Greenwood Publishing Group|year=1995|pages=73|isbn=978-0-89391-828-6|oclc=2009-06-12|url=http://books.google.com/?id=VPXAxkTKxXIC}}</ref>

<code>
1 '''function''' Kernighan-Lin(''G(V,E)''):
2 determine a balanced initial partition of the nodes into sets A and B
3 A1 := A; B1 := B
4 '''do'''
5 compute D values for all a in A1 and b in B1
6 '''for (n := 1 to |V|/2)'''
7 find a[i] from A1 and b[j] from B1, such that g[n] = D[a[i]] + D[b[j]] - 2*c[a[i]][b[j]] is maximal
8 move a[i] to B1 and b[j] to A1
9 remove a[i] and b[j] from further consideration in this pass
10 update D values for the elements of A1 = A1 \ a[i] and B1 = B1 \ b[j]
11 '''end for'''
12 find k which maximizes g_max, the sum of g[1],...,g[k]
13 '''if (g_max > 0)''' '''then'''
14 Exchange a[1],a[2],...,a[k] with b[1],b[2],...,b[k]
15 '''until (g_max <= 0)'''
16 '''return G(V,E)'''
</code>

==References==
{{reflist}}

{{DEFAULTSORT:Kernighan-Lin algorithm}}
[[Category:Combinatorial optimization]]
[[Category:Combinatorial algorithms]]
[[Category:Heuristic algorithms]]

formulasearchengine - User contributions [en]

M-spline