文档介绍：.;.-.‘,,’<’
I
/--
1. .
..*
tr EFFIC'IENTALGORITHMS FOR GRAPHMANIPULATION
BY
JOHNHOPCROFT
ROBERTTARJAN
STAN-CS-71-207
MARCH, 1971
COMPUTER SCIENCE DEPARTMENT
School of Humanities and Sciences
STANFORD UNIVERSITY
Efficient Algorithms for Graph Manipulation
a.
John Hopcroft
Robert Tarjan
Stanford University, Stanford, California
Abstract: Efficient algorithms are presented for partitioning a graph
into ponents, ponents and simple paths.
--.
The algorithm for partitioning of a graph into simple paths is
iterative and each iteration produces a new path between two
vertices already on paths. (The start vertex can be specified
dynamically.) If V is the number of vertices and E is the number
of edges each algorithm requires time and space proportional-to
max(V,E) when executed on a randam puter.
This research was supported by the Hertz Foundation and by the Office
of Naval Research under grant number N-00014-67-A-0112-005'7 NR 044-402.
Reproduction in whole or in part is permitted for any purpose of the
United States Government.
EFFICIENT ALGORITHMS FOR GRAPH MANIIULATION
John Hopcroft
Robert Tarjan
Stanford University, Stanford, California
Graphs arise in many different contexts where it is necessary to represent interrelations between data
elements. Consequently algorithms are being developed to manipulate graphs and test them for various
properties. Certain basic tasks mon to many of these algorithms. For example, in order to test a
graph for planarity, one first poses the graph-into ponents and tests ponent
separately. If one is using an algorithm [4] with asymptotic growth of V log V to test for planarity, it
is imperative that one use an algorithm for partitioning the graph whose asymptotic growth is linear with the
number of edges rather than quadratic in the number of vertices. In fact, representing a graph by a connection
matrix in the above case would result in spending more time in constru