Maintaining longest paths incrementally

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

Laurent Michel, Irit Katriel, Pascal Van Hentenryck

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

graphschedulinglocal searchconstraintlongest pathincrementalbounded computationheaviest path

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

Heuristic approaches for scheduling jobs in large-scale flexible job shops ⋮ Accelerating the calculation of makespan used in scheduling improvement heuristics ⋮ A general efficient neighborhood structure framework for the job-shop and flexible job-shop scheduling problems ⋮ A dynamic topological sort algorithm for directed acyclic graphs ⋮ A batch-oblivious approach for complex job-shop scheduling problems

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

This page was built for publication: Maintaining longest paths incrementally