Show simple item record

dc.contributor.authorJaumard, Brigitte
dc.contributor.authorMinoux, Michel
dc.date.accessioned2014-08-28T12:48:45Z
dc.date.available2014-08-28T12:48:45Z
dc.date.issued1986
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/13869
dc.language.isoenen
dc.subjectTransitive closure of a directed graphen
dc.subjectcomplexity of transitive closureen
dc.subjectlist processingen
dc.subjectdata structuresen
dc.subject.ddc005en
dc.titleAn efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenComputing the transitive closure of a directed graph can be reduced to determining the transitive closure of the (circuit-free) 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 circuit-free graph, the complexity of which (in the worst-case 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 in-degrees bounded by some fixed constant K, we show that our algorithm is linear in M′, the number of arcs in the transitive closure.en
dc.relation.isversionofjnlnameInformation Processing Letters
dc.relation.isversionofjnlvol22en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate1986
dc.relation.isversionofjnlpages163-169en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/0020-0190(86)90021-9en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record