2005 | OriginalPaper | Chapter
Maintaining Longest Paths in Cyclic Graphs
Authors : Irit Katriel, Pascal Van Hentenryck
Published in: Principles and Practice of Constraint Programming - CP 2005
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper reconsiders the problem of maintaining longest paths in directed graphs, which is at the core of many scheduling applications. It presents bounded incremental algorithms for arc insertion and deletion running in time
O
(||
δ
|| + |
δ
|
log
|
δ
|) on Cyclic<0 graphs (i.e., graphs whose cycles have strictly negative lengths), where |
δ
| and ||
δ
|| are measures of the change in the input and output. For Cyclic≤0 graphs, maintaining longest paths is unbounded under reasonable computational models; when only arc insertions are allowed, it is shown that the problem can be solved in
O
(||
δ
|| + |
δ
|
log
|
δ
|) time even in the presence of zero-length cycles. The algorithms directly apply to shortest paths (by negating the lengths), leading to simpler algorithms than previously known and reducing the worst-case complexity of an operation from Õ(
n
m
) to
O
(
n
+
m
) for Cyclic>0 graphs with
n
vertices and
m
arcs.