Name
Abstract | ||
|---|---|---|
Modeling and programming tools for neighborhood search often support invariants, i.e., data structures specified declaratively and automatically maintained incrementally under changes. This paper considers invariants for longest paths in directed acyclic graphs, a fundamental abstraction for many applications. It presents bounded incremental algorithms for arc insertion and deletion which run in O(驴驴驴 + |驴| log|驴|) time and O(驴驴驴) time respectively, where |驴| and 驴驴驴 are measures of the change in the input and output. The paper also shows how to generalize the algorithm to various classes of multiple insertions/deletions encountered in scheduling applications. Preliminary experimental results show that the algorithms behave well in practice. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/s10601-005-0554-9 | Constraints |
Keywords | Field | DocType |
incremental,longest path,heaviest path,bounded computation,graph,constraint,local search,scheduling | Data structure,Discrete mathematics,Mathematical optimization,Computer science,Algorithm,Directed graph,Combinatorial optimization,Input/output,Directed acyclic graph,Local search (optimization),Longest path problem,Bounded function | Journal |
Volume | Issue | ISSN |
10 | 2 | 1383-7133 |
Citations | PageRank | References |
5 | 0.48 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irit Katriel | 1 | 176 | 13.72 |
| Laurent Michel | 2 | 441 | 37.61 |
| Pascal Van Hentenryck | 3 | 4052 | 425.66 |