Average-Case Analysis of Online Topological Ordering
From MaRDI portal
Publication:5387779
DOI10.1007/978-3-540-77120-3_41zbMATH Open1193.68183OpenAlexW1549024371MaRDI QIDQ5387779FDOQ5387779
Authors: Deepak Ajwani, Tobias Friedrich 
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
Recommendations
- Average-case analysis of incremental topological ordering
- An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering
- An O ( n 2.75 ) algorithm for incremental topological ordering
- An algorithm for online topological ordering
- A tight analysis of the Katriel-Bodlaender algorithm for online topological ordering
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Random graphs.
- A dynamic topological sort algorithm for directed acyclic graphs
- Algorithms – ESA 2004
- On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- Online topological ordering
- On the computational complexity of dynamic graph problems
- Incremental algorithms for minimal length paths
- A phase transition phenomenon in a random directed acyclic graph
- Title not available (Why is that?)
- Title not available (Why is that?)
- Online topological ordering
- Maintaining a topological order under edge insertions
- A uniform approach to semi-dynamic problems on digraphs
- An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering
- On competitive on-line algorithms for the dynamic priority-ordering problem
Cited In (1)
This page was built for publication: Average-Case Analysis of Online Topological Ordering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387779)
