Maintaining longest paths incrementally

DOI10.1007/s10601-005-0554-9zbMath1084.68027MaRDI QIDQ816679

Pascal Van Hentenryck, Laurent Michel, Irit Katriel

Publication date: 23 February 2006

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10601-005-0554-9

zbMATH Keywords

graph; scheduling; local search; constraint; longest path; incremental; bounded computation; heaviest path

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68P05: Data structures

Related Items

A dynamic topological sort algorithm for directed acyclic graphs

Uses Software

• iOpt
• SALSA
• COMET
• EasyLocal++
• Localizer++
• Localizer

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple tabu search for warehouse location
• Temporal constraint networks
• Solving systems of difference constraints incrementally
• On the computational complexity of dynamic graph problems
• Insertion techniques for the heuristic solution of the job shop problem
• Improved local search for CP toolkits
• Optimization software class libraries
• SALSA: a language for search algorithms
• A general approach for constraint solving by local search
• Localizer
• Applying tabu search to the job-shop scheduling problem
• Amortized Computational Complexity
• A Computational Study of Local Search Algorithms for Job Shop Scheduling
• A Fast Taboo Search Algorithm for the Job Shop Problem
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Principles and Practice of Constraint Programming – CP 2003
• Integer priority queues with decrease key in constant time and the single source shortest paths problem