English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Conference Paper

Dynamic Heaviest Paths in DAGs with Arbitrary Edge Weights

MPS-Authors
/persons/resource/persons44744

Katriel,  Irit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Katriel, I. (2004). Dynamic Heaviest Paths in DAGs with Arbitrary Edge Weights. In Integration of AI and OR techniques in constraint programming for combinatorial optimization problems: First International Conference, CPAIOR 2004 (pp. 190-199). Berlin, Germany: Springer.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2A7A-E
Abstract
We deal with the problem of maintaining the heaviest paths in a DAG under edge insertion and deletion. Michel and Van Hentenryck~\cite{Michel} designed algorithms for this problem which work on DAGs with strictly positive edge weights. They handle edges of zero or negative weight by replacing each of them by (potentially many) edges with positive weights. In this paper we show an alternative solution, which has the same complexity and handles arbitrary edge weights without graph transformations. For the case in which all edge weights are integers, we show a second algorithm which is asymptotically faster.