Maintaining longest paths incrementally

DOI10.1007/S10601-005-0554-9MaRDI QIDQ816679zbMATH OpenOpenAlexFDO

Authors Irit Katriel, Laurent Michel, 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

graphlocal searchconstraintschedulinglongest pathincrementalbounded computationheaviest path

Mathematics Subject Classification ID

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

Recommendations

• Maintaining longest paths incrementally
• Maintaining Longest Paths in Cyclic Graphs
• Incremental algorithms for minimal length paths
• Longest increasing paths with gaps
• scientific article; zbMATH DE number 3974318
• Dynamically maintaining shortest path trees under batches of updates
• On approximating the longest path in a graph
• Longest increasing paths with Lipschitz constraints
• Algorithms for long paths in graphs
• Longest paths joining given vertices in a graph

Cites work

• scientific article; zbMATH DE number 432748 (Why is no real title available?)
• scientific article; zbMATH DE number 2084750 (Why is no real title available?)
• scientific article; zbMATH DE number 2083802 (Why is no real title available?)
• A Computational Study of Local Search Algorithms for Job Shop Scheduling
• A Fast Taboo Search Algorithm for the Job Shop Problem
• A general approach for constraint solving by local search
• A simple tabu search for warehouse location
• Amortized Computational Complexity
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• Applying tabu search to the job-shop scheduling problem
• Improved local search for CP toolkits
• Insertion techniques for the heuristic solution of the job shop problem
• Integer priority queues with decrease key in constant time and the single source shortest paths problem
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Localizer
• Maintaining longest paths incrementally
• On the computational complexity of dynamic graph problems
• Online topological ordering
• Optimization software class libraries
• SALSA: a language for search algorithms
• Solving systems of difference constraints incrementally
• Temporal constraint networks

Cited in

(7)

• A batch-oblivious approach for complex job-shop scheduling problems
• Maintaining Longest Paths in Cyclic Graphs
• Accelerating the calculation of makespan used in scheduling improvement heuristics
• Heuristic approaches for scheduling jobs in large-scale flexible job shops
• 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
• Maintaining longest paths incrementally

Describes a project that uses

Uses Software

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

This page was built for publication: Maintaining longest paths incrementally

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q816679)