Skip to main content
Top

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.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadata
Title
Maintaining Longest Paths in Cyclic Graphs
Authors
Irit Katriel
Pascal Van Hentenryck
Copyright Year
2005
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/11564751_28

Premium Partner