Depth-First Search and Linear Graph Algorithms

ISCAS OpenIR

	Depth-First Search and Linear Graph Algorithms
	Robert Tarjan
	1972
发表期刊	SIAM Journal on Computing
卷号	1 期号:2 页码:146-160
摘要	The value of depth-first search or "backtracking" as a technique for solving problems is illustrated by two examples. An improved version of an algorithm for finding the strongly connected components of a directed graph and at algorithm for finding the biconnected components of an undirect graph are presented. The space and time requirements of both algorithms are bounded by $k_1 V + k_2 E + k_3 $ for some constants $k_1 ,k_2 $, and $k_3 $, where $V$ is the number of vertices and $E$ is the number of edges of the graph being examined.
收录类别	其他
合作性质	其它
语种	英语
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/1322
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Robert Tarjan. Depth-First Search and Linear Graph Algorithms[J]. SIAM Journal on Computing,1972,1(2):146-160.
APA	Robert Tarjan.(1972).Depth-First Search and Linear Graph Algorithms.SIAM Journal on Computing,1(2),146-160.
MLA	Robert Tarjan."Depth-First Search and Linear Graph Algorithms".SIAM Journal on Computing 1.2(1972):146-160.