ON FINDING THE STRONGLY CONNECTED COMPONENTS IN A DIRECTED GRAPH

作     者：NUUTILA, E SOISALONSOININEN, E 

作者机构：Laboratory of Information Processing Science Department of Computer Science Helsinki University of Technology Otakaari 1M SF-02150 Espoo Finland 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：1994年第49卷第1期

页      面：9-14页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：DESIGN OF ALGORITHMS STRONGLY CONNECTED COMPONENTS TARJANS ALGORITHM TRANSITIVE CLOSURE 

摘      要：We present two improved versions of Tarjan s algorithm for the detection of strongly connected components in a directed graph. Our new algorithms handle sparse graphs and graphs with many trivial components (containing only one node) more economically than Tarjan s original algorithm. As an application we present an efficient transitive closure algorithm.