Institutional Repository
| Depth-First Search and Linear Graph Algorithms | |
| Robert Tarjan | |
| 1972 | |
| Source | SIAM Journal on Computing
 |
| Volume | 1Issue:2Pages:146-160 |
| English Abstract | 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. |
| Indexed Type | 其他 |
| Cooperation Status | 其它 |
| Language | 英语 |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/1322 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation 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. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| bj01134931.pdf（1915KB） | 开放获取 | License | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment