de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Dynamic Heaviest Paths in DAGs with Arbitrary Edge Weights

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44744

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-2A7A-E
Zusammenfassung
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.