Average-case analysis of incremental topological ordering

DOI10.1016/J.DAM.2009.07.006MaRDI QIDQ968137zbMATH OpenOpenAlexFDO

Authors Deepak Ajwani, Tobias Friedrich

Publication date 5 May 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10197/10132

zbMATH Keywords

average-case analysisrandom graphsdynamic graph algorithms

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Average-Case Analysis of Online Topological Ordering
• An O ( n ^2.75 ) algorithm for incremental topological ordering
• A dynamic topological sort algorithm for directed acyclic graphs
• Faster Algorithms for Incremental Topological Ordering
• Maintaining a topological order under edge insertions

Cites work

• scientific article; zbMATH DE number 432748 (Why is no real title available?)
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1305092 (Why is no real title available?)
• A dynamic topological sort algorithm for directed acyclic graphs
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• A new approach to incremental topological ordering
• A phase transition phenomenon in a random directed acyclic graph
• A uniform approach to semi-dynamic problems on digraphs
• Algorithms – ESA 2004
• An O ( n ^2.75 ) algorithm for incremental topological ordering
• An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering
• Average-Case Analysis of Online Topological Ordering
• Degree sequences of random graphs
• Faster Algorithms for Incremental Topological Ordering
• Incremental algorithms for minimal length paths
• Maintaining a topological order under edge insertions
• On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
• On the computational complexity of dynamic graph problems
• Online topological ordering
• Online topological ordering
• Paths in graphs

Cited in

(3)

• Average-Case Analysis of Online Topological Ordering
• An O ( n ^2.75 ) algorithm for incremental topological ordering
• Topological sorts on DAGs

Describes a project that uses

Uses Software

• Sather

This page was built for publication: Average-case analysis of incremental topological ordering

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