Name
Abstract | ||
|---|---|---|
Abstract. It is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting m edges can be solved in O(min{m, n) for general k and that it can be implemented to run in O(n log n) time on trees, which is optimal. If the input contains cycles, the algorithm detects this. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1159892.1159896 | ACM Transactions on Algorithms |
Keywords | DocType | Volume |
topological order,treewidth,online algorithms,graphs,dynamic algorithms | Journal | 2 |
Issue | ISSN | Citations |
3 | 1549-6325 | 8 |
PageRank | References | Authors |
0.57 | 11 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irit Katriel | 1 | 176 | 13.72 |
| Hans L. Bodlaender | 2 | 5699 | 375.15 |