Robert Endre Tarjan (born April 30, 1948) is an American Computer

---

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