Robert C. Prim
Encyclopedia
Robert Clay Prim is an American
mathematician
and computer scientist
.
In 1941, Prim received his B.S. in Electrical Engineering
from Princeton University
. Later in 1949, he received his Ph.D. in Mathematics
there also. Robert Prim worked at Princeton University
from 1948 until 1949 as a research associate.
During the climax of World War II
(1941–1944), Prim worked as an engineer for General Electric
. From 1944 until 1949, he was hired by the United States Naval Ordnance Lab as an engineer and later a mathematician. At Bell Laboratories
, he served as director of mathematics research from 1958 to 1961. There, Prim developed Prim's algorithm
. After Bell Laboratories, Prim became vice president of research at Sandia National Laboratories
.
During his career at Bell Laboratories, Robert Prim along with coworker Joseph Kruskal
developed two different algorithms (see greedy algorithm
) for finding a minimum spanning tree
in a weighted graph
, a basic stumbling block in computer network design
. His self named algorithm, Prim's algorithm, was originally discovered in 1930 by mathematician Vojtěch Jarník
and later independently by Prim in 1957. It was later rediscovered by Edsger Dijkstra
in 1959. It is sometimes referred to as the DJP algorithm or the Jarník algorithm.
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
and computer scientist
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
.
In 1941, Prim received his B.S. in Electrical Engineering
Electrical engineering
Electrical engineering is a field of engineering that generally deals with the study and application of electricity, electronics and electromagnetism. The field first became an identifiable occupation in the late nineteenth century after commercialization of the electric telegraph and electrical...
from Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
. Later in 1949, he received his Ph.D. in Mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
there also. Robert Prim worked at Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
from 1948 until 1949 as a research associate.
During the climax of World War II
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
(1941–1944), Prim worked as an engineer for General Electric
General Electric
General Electric Company , or GE, is an American multinational conglomerate corporation incorporated in Schenectady, New York and headquartered in Fairfield, Connecticut, United States...
. From 1944 until 1949, he was hired by the United States Naval Ordnance Lab as an engineer and later a mathematician. At Bell Laboratories
Bell Labs
Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...
, he served as director of mathematics research from 1958 to 1961. There, Prim developed Prim's algorithm
Prim's algorithm
In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...
. After Bell Laboratories, Prim became vice president of research at Sandia National Laboratories
Sandia National Laboratories
The Sandia National Laboratories, managed and operated by the Sandia Corporation , are two major United States Department of Energy research and development national laboratories....
.
During his career at Bell Laboratories, Robert Prim along with coworker Joseph Kruskal
Joseph Kruskal
Joseph Bernard Kruskal, Jr. was an American mathematician, statistician, computer scientist and psychometrician. He was a student at the University of Chicago and at Princeton University, where he completed his Ph.D. in 1954, nominally under Albert W...
developed two different algorithms (see greedy algorithm
Greedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
) for finding a minimum spanning tree
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
in a weighted graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
, a basic stumbling block in computer network design
Computer network
A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
. His self named algorithm, Prim's algorithm, was originally discovered in 1930 by mathematician Vojtěch Jarník
Vojtech Jarník
Vojtěch Jarník was a Czech mathematician.His main area of work was in number theory and mathematical analysis; he proved a number of results on lattice point problems. He also developed the graph theory algorithm known as Prim's algorithm....
and later independently by Prim in 1957. It was later rediscovered by Edsger Dijkstra
Edsger Dijkstra
Edsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...
in 1959. It is sometimes referred to as the DJP algorithm or the Jarník algorithm.