Joseph Kruskal was an American mathematician best known in computer science for Kruskals algorithm, published in 1956, a greedy method for finding the minimum spanning tree of a weighted graph by repeatedly adding the cheapest edge that does not create a cycle. The algorithm remains a standard tool for problems such as designing and pricing communication and transportation networks at minimum cost, and it is taught alongside Prims algorithm as one of the two classic solutions to the minimum spanning tree problem.
Facts
AwardFellow of the American Statistical Association 2 FAQs
What is a minimum spanning tree, the problem Kruskal's algorithm solves?
A minimum-weight tree that connects every vertex of a weighted graph.
A minimum spanning tree is a minimum-weight tree in a weighted graph that contains all of the graph's vertices. It is also called a shortest spanning tree, and the term is more common in operations research. Besides Kruskal's algorithm, the NIST Dictionary of Algorithms and Data Structures lists Prim-Jarnik and Boruvka's algorithms as related methods, and notes that a minimum spanning tree can be used to quickly find a near-optimal solution to the traveling salesman problem.
Connections
Credited
Source Wikipedia, Kruskal's algorithm
Source Wikipedia, Prim's algorithm
In Field
Source Wikipedia: Joseph Kruskal
Invented
Joseph Kruskal published the minimum spanning tree algorithm bearing his name in 1956.
Source Wikipedia, Prim's algorithm
In the Other Atlases
Same As
Also in Mathematics Atlas: the same subject.
Nationality
Also in Geography Atlas: the nationality of this subject.
Sources
1. Wikipedia: Joseph Kruskal
Wikimedia FoundationLead section
Joseph Bernard Kruskal, Jr. (; January 29, 1928 - September 19, 2010) was an American mathematician.
In Field: Algorithms and Complexity Theory, Infobox: known_for
Multidimensional scaling Kruskal's algorithm Kruskal's tree theorem Kruskal-Katona theorem
View the Source 2. Wikidata: Joseph Kruskal
Wikidata Q983361, class allow-list match (w-wdresolver-0926)View the Source Wikipedia, Prim's algorithm
Invented: Prim's Algorithm, Lead section
The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later rediscovered and republished by Joseph Kruskal in 1956, Robert C. Prim in 1957, and Edsger W. Dijkstra in 1959.
Credited: Prim's Algorithm, Lead paragraph
later rediscovered and republished by Joseph Kruskal in 1956, Robert C. Prim in 1957, and Edsger W. Dijkstra in 1959
View the SourceWikipedia, Kruskal's algorithm
Credited: Kruskal's Algorithm, Lead paragraphQuote, Credited: Kruskal's Algorithm, Lead paragraph
This algorithm was first published by Joseph Kruskal in 1956
Reader 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.