Notes on oriented depth-first search and longest paths (Q1118610)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Notes on oriented depth-first search and longest paths |
scientific article; zbMATH DE number 4095499
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Notes on oriented depth-first search and longest paths |
scientific article; zbMATH DE number 4095499 |
Statements
Notes on oriented depth-first search and longest paths (English)
0 references
1989
0 references
Simple acyclic directed graphs having a depth-first search tree with no cross edges are characterized; this leads to a linear time algorithm for finding such a DFS tree, via a reduction to the longest path problem in such digraphs. Applications to drawing flowcharts are outlined.
0 references
directed acyclic graphs
0 references
depth-first search
0 references
longest path
0 references
flowcharts
0 references
