Average-Case Analysis of Online Topological Ordering

DOI10.1007/978-3-540-77120-3_41zbMath1193.68183OpenAlexW1549024371MaRDI QIDQ5387779

Tobias Friedrich, Deepak Ajwani

Publication date: 27 May 2008

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77120-3_41

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

Average-case analysis of incremental topological ordering

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A uniform approach to semi-dynamic problems on digraphs
• On competitive on-line algorithms for the dynamic priority-ordering problem
• On the computational complexity of dynamic graph problems
• Maintaining a topological order under edge insertions
• Online topological ordering
• On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
• A dynamic topological sort algorithm for directed acyclic graphs
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• Incremental algorithms for minimal length paths
• Algorithms – ESA 2004
• An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering

This page was built for publication: Average-Case Analysis of Online Topological Ordering