taktoa
commented
6 years ago Average-case analysis of incremental topological ordering examines the average-case behavior of some of the incremental SCC algorithms that were superceded in the paper by Bender et al. mentioned above. Might be worth seeing if there are any papers on the average-case performance of the Bender algorithm.
Other relevant questions:
- What is the worst/average-case asymptotic space complexity of these algorithms?
- Are any data structures used by these algorithms as black boxes? When implementing, we will want to choose the best implementation of these data structures. IIRC, the algorithm described in Bender et al. uses a union-find data structure, so depending on its size, Succinct Data Structures for Representing Equivalence Classes and Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure (which finds that the algorithm described on page 192 / chapter 25 of A Discipline of Programming is the best union-find implementation in practice despite having bad asymptotic complexity).
It seems like it would be quite useful (e.g.: for implementing perfect sharing) to maintain the graph of strongly-connected components of a PEG/EPEG while we build up the graph. The current state of the art online algorithm for computation of strongly-connected components is described in A New Approach to Incremental Cycle Detection and Related Problems. Technically there are two algorithms described in that paper: one that has the best known complexity bound for sparse graphs and one that has the best bound for dense graphs. It seems likely to me that PEGs are mostly going to be sparse, though I may be underestimating the amount of sharing they have. Of course, in this regime I suspect the constant factors may matter more than the difference between an
O(min(m^{3/2}, mn^{2/3}))algorithm and anO(n^2 log(n))algorithm.