Jump to content

Kernighan–Lin algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Ruud Koot (talk | contribs) at 22:00, 10 June 2009 (←Created page with ': ''This article is about the heuristic algorithm for the graph partitioning problem. For a heuristic for the traveling salesman problem, see [[Lin–Kernighan heur…'). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)
This article is about the heuristic algorithm for the graph partitioning problem. For a heuristic for the traveling salesman problem, see Lin–Kernighan heuristic.

In combinatorial optimization, Kernighan–Lin is a heuristic algorithm for solving the graph partitioning problem.


References

  • Kernighan, B. W.; Lin, Shen (1970). "An efficient heuristic procedure for partitioning graphs". Bell Systems Technical Journal. 49: 291–307.
Stub icon

This computer science article is a stub. You can help Wikipedia by expanding it.

Stub icon

This applied mathematics–related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Kernighan–Lin_algorithm&oldid=295664792"