The constrained shortest path problem: algorithmic approaches and an algebraic study with generalization (Q2369383): Difference between revisions

This article presents an overview of algorithms for the constrained shortest path problem. This problem is an \(NP\)-hard problem that has been studied extensively in the context of telecommunications and computer science. The authors start by describing the existing approximation and heuristics algorithms, followed by a precise mathematical formulation of the problem. The next section studies the equivalence of a class of algorithms for the constrained path problem, which is then followed by an algebraic study of the relaxation of the problem. The fourth and fifth sections of the article investigate binary search type algorithms which are based on algorithms already described earlier, followed by parametric search based algorithms. The article concludes with a section containing simulation results and an extensive list of references.