History
December 13, 2013
Robert Endre Tarjan (born April 30, 1948) is an American Computer
Scientist. He is the discoverer of several graph algorithms, including Tarjan’s
offline least common ancestors algorithm, and co-inventor of both splay trees
and Fibonacci heaps. Tarjan is currently the James S. McDonnell Distinguished
University Professor of Computer Science at Princeton University, and is also
a Senior Fellow at Hewlett-Packard. He was born in Pomona, California. As a
child, Tarjan read a lot of science fiction, and wanted to be an astronomer. He
became interested in mathematics after reading Martin Gardner’s mathematical
games column in Scientific American. He became seriously interested in math
in the eighth grade, thanks to a “very stimulating”teacher.
While he was in high school, Tarjan got a job, where he worked IBM card
punch collators. He first worked with real computers while studying astronomy
at the Summer Science Program in 1964. Tarjan obtained a Bachelor’s degree in
mathematics from the California Institute of Technology in 1969. At Stanford
University, he received his Master’s degree in computer science in 1971 and
a Ph.D. in computer science (with a minor in mathematics) in 1972. Tarjan
has designed many efficient algorithms and data structures. Some of his well-
known algorithms include Tarjan’s off-line least common ancestors algorithm,
and Tarjan’s strongly connected components algorithm Tarjan’s Algorithm.
A Depth First Search begins from an arbitrary start node and subsequent
depth first searches are conducted on any nodes that have not yet been found.
A susual with depth first search, the search visits every node of the graph ex-
actly once, declining to revisit any node that has already been explored. Thus,
the collect ion of search trees is a spanning forest of the graph. The strongly
connected components will be recovered as certain subtrees of this forest. The
classic sequential al gorithm for computing biconnected components in a con-
nected undirected graph due to John Hopcroft and Robert Tarjan (1973) runs
in linear time, and is based on depth first search.
The classic sequential algorithm for computing biconnected components in
a connected undirected graph due to John Hopcroft and Robert Tarjan in
1973 runs in a linear time, and is based on depth first search. John Edward
Hopcroft was born in October 7, 1939 is an American theoritical computer
scientist. His te xtbooks on theory of computation also known as the Cindrella
book and data structures are regarded as standards in their fields. He is the
IBM Professor of Engineering and Applied Mathematics in Computer Science at
1
Cornell University. In 1986 he received the Turing Award, the most prestigious
award in the field and often recognized as the “Nobel Prize of Computing”
jointly with Robert Tarjan “for fundamental achievements in the design and
analysis of algorithms and data structures”. Along with his work with Tarjan
on planar graphs he is also known for the Hopcroft-Karp algorithm for finding
matchings in bipartite graphs.
A version of depth first search was investigated in the 19th century by French
mathematician Charles Pierre Trmaux as a strategy for solving mazes. In a
depth first search of a graph, the tree of edges by which each vertex was first
reached (also called a depth first search tree) is necessarily a Trmaux tree.
Trmaux trees a renamed after Charles Pierre Trmaux, a 19th-century French
author who used a form of depth first search as a strategy for solving mazes.
Using Depth First Search as main building block there are several applica-
tions one of them is solving mazes and finding biconnectivity of graph. Bicon-
nected graphs were introduced by Skiena in 1990 and later developed by Haray
in 1994.
2