Notes on oriented depth-first search and longest paths
type: Item
instance of: scholarly article
title: Notes on oriented depth-first search and longest paths
zbMATH Open document ID: 0669.05039
DOI: 10.1016/0020-0190(89)90109-9
author: Hideki Imai
author: Hubert de Fraysseix
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4095499
zbMATH Keywords: directed acyclic graphs
zbMATH Keywords: depth-first search
zbMATH Keywords: longest path
zbMATH Keywords: flowcharts
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90109-9
OpenAlex ID: W2071681494
cites work: Characterizations of Reducible Flow Graphs
cites work: Testing flow graph reducibility
cites work: Finding Dominators in Directed Graphs
description: scientific article; zbMATH DE number 4095499