News Help Institutional access
Back to results
Bibliographic record · Consultation and access
Artículo

Depth-First Search and Linear Graph Algorithms

Robert E. Tarjan · SIAM Journal on Computing · 1972

Supplementary material available
Quick overview. Review the resource’s basic details, then access the content using the main button. This page shows only the information needed to identify, cite, and open the work.
Author / responsible party
Robert E. Tarjan
Publisher
SIAM Journal on Computing
Year
1972
Language
English

Resource access

Open the content from the main option or choose another available source.

OpenAlex OpenAlex Works
Entrar por OpenAlex
Main access

Supplementary material available

El enlace apunta a material asociado, anexos, tablas, datos o página complementaria. No se marca como libro/texto completo.
Open material

Summary

Descripción general del contenido del recurso.

Abstract. The value of depth-first search or "bacltracking " 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 ar algorithm for finding the biconnected components of an undirect graph are presented. The space and time requirements of both algorithms are bounded by k 1V + k2E d- k for some constants kl, k2, and k a, where Vis the number of vertices and E is the number of edges of the graph being examined.

How to cite

Elegí el formato que necesitás y copiá la referencia al portapapeles.

APA 7

Tarjan, R. E. (1972). Depth-First Search and Linear Graph Algorithms. https://doi.org/10.1137/0201010

MLA

Tarjan, Robert E. "Depth-First Search and Linear Graph Algorithms." 1972. https://doi.org/10.1137/0201010.

Chicago

Tarjan, Robert E. 1972. "Depth-First Search and Linear Graph Algorithms.". https://doi.org/10.1137/0201010.

Harvard

Tarjan, R. E. 1972, Depth-First Search and Linear Graph Algorithms, SIAM Journal on Computing, available at: https://doi.org/10.1137/0201010 [Accessed 7 Aug. 2026].

Share and print

Save the record, copy its permanent link, or print it as a PDF.

Export reference

You can export the record in common formats for use in a reference manager.

RIS BibTeX

Resource details

Bibliographic information to help confirm that this is the correct material.

Title
Depth-First Search and Linear Graph Algorithms
Author / contributors
Robert E. Tarjan
Publisher
SIAM Journal on Computing
Publication year
1972
Language
English

Subjects

Explore related resources through these subjects.

Backtracking; Combinatorics; Graph; Mathematics; Algorithm; Graph algorithms; Depth-first search; Complement graph; Bounded function; Discrete mathematics; Line graph; Graph power
Copied