scientific article; zbMATH DE number 512931

MaRDI QIDQ4281646zbMATH OpenFDO

Authors Mikkel Thorup

Publication date 10 March 1994

zbMATH Keywords

digraphsparallel computationreachabilitytransitive closure

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Shortcutting Planar Digraphs
• scientific article; zbMATH DE number 2079397
• Nearly work-efficient parallel algorithm for digraph reachability
• Nearly work-efficient parallel algorithm for digraph reachability
• On the parallel complexity of digraph reachability

Cited in

(15)

• Dynamic tree shortcut with constant degree
• Steiner transitive-closure spanners of low-dimensional posets
• scientific article; zbMATH DE number 2079397 (Why is no real title available?)
• A hierarchy of lower bounds for sublinear additive spanners
• Shortcutting Planar Digraphs
• Transitive-closure spanners: a survey
• Shortcutting directed and undirected networks with a degree constraint
• scientific article; zbMATH DE number 7238981 (Why is no real title available?)
• Nearly work-efficient parallel algorithm for digraph reachability
• Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
• Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
• Are there graphs whose shortest path structure requires large edge weights?
• Efficient provably-secure hierarchical key assignment schemes
• Giving some slack: shortcuts and transitive closure compressions
• New constructions for provably-secure time-bound hierarchical key assignment schemes

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4281646)