An efficient algorithm for the transitive closure and a linear worstcase complexity result for a class of sparse graphs
Jaumard, Brigitte; Minoux, Michel (1986), An efficient algorithm for the transitive closure and a linear worstcase complexity result for a class of sparse graphs, Information Processing Letters, 22, 4, p. 163169. http://dx.doi.org/10.1016/00200190(86)900219
Type
Article accepté pour publication ou publiéDate
1986Journal name
Information Processing LettersVolume
22Number
4Publisher
Elsevier
Pages
163169
Publication identifier
Metadata
Show full item recordAbstract (EN)
Computing the transitive closure of a directed graph can be reduced to determining the transitive closure of the (circuitfree) graph induced on the strongly connected components (the transitive closure of a strongly connected graph being the complete graph). A new algorithm is described to compute the transitive closure of a circuitfree graph, the complexity of which (in the worstcase sense) is better than O(MN) (M being the number of arcs and N the number of vertices). In the case of low density graphs, the resulting complexity is then better that that of previously known algorithms. In particular, for the class of low density circuitless graphs with vertices having indegrees bounded by some fixed constant K, we show that our algorithm is linear in M′, the number of arcs in the transitive closure.Subjects / Keywords
Transitive closure of a directed graph; complexity of transitive closure; list processing; data structuresRelated items
Showing items related by title and author.

Della Croce, Federico; Escoffier, Bruno; Kaminski, Marcin; Paschos, Vangelis (2008) Chapitre d'ouvrage

Hansen, Pierre; Jaumard, Brigitte; Minoux, Michel (1986) Article accepté pour publication ou publié

Paschos, Vangelis; Della Croce, Federico; Escoffier, Bruno (2007) Article accepté pour publication ou publié

Paschos, Vangelis; Della Croce, Federico (2008) Article accepté pour publication ou publié

Bourgeois, N.; Catellier, Rémi; Denat, T.; Paschos, Vangelis (2015) Document de travail / Working paper