The Kernighan-Lin algorithm is a heuristic method for finding good partitions of a graph. It has important practical application in the layout of digital circuits and components during electronic design automation for very large scale integration. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 1 Classification
Design TechniqueHeuristic or Approximation 1 Connections
In Field
Source Wikipedia: Kernighan-Lin algorithm
Uses Design Technique
Sources
1. Wikipedia: Kernighan-Lin algorithm
Lead section
The Kernighan-Lin algorithm is a heuristic algorithm for finding partitions of graphs.
In Field: Algorithms and Complexity Theory, Lead sentence
Kernighan-Lin algorithm is a heuristic algorithm for finding partitions of graphs.
In Group: Graph Cut and Partitioning Algorithms, Lead
The Kernighan-Lin algorithm is a heuristic algorithm for finding partitions of graphs.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.