Network reduction for the acyclic constrained shortest path problem
type: Item
instance of: scholarly article
title: Network reduction for the acyclic constrained shortest path problem
zbMATH Open document ID: 0764.90085
DOI: 10.1016/0377-2217(92)90060-M
author: Mohsen M. D. Hassan
published in: European Journal of Operational Research
publication date: 1993-04-01T00:00:00Z
review text: The paper is about minimizing the length \(d(P)\) of a path \(P\) from a source \(r\) to a sink \(t\) in an acyclic digraph \(G\); moreover, \(P\) must be admissible, i.e. the time \(t(P)\) caused by the path \(P\) must not exceed a fixed limit \(T\). The main idea is to reduce the given graph by removing nodes \(v\) and arcs \(a\) which cannot be visited by any admissibe path; a typical case is that \(t(P')>T\) for all paths \(P'\) from \(r\) to \(v\). The author gives several situations in which \(v\) or \(a\) can be deleted, and he describes some practical tests of this method.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C08
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 149249
zbMATH Keywords: shortest path
zbMATH Keywords: transportation
zbMATH Keywords: acyclic digraph
MaRDI profile type: Publication
cites work: The constrained shortest path problem
cites work: A bicriterion shortest path algorithm
cites work: Note on Multiple Objective Dynamic Programming
cites work: Shortest-path algorithms: Taxonomy and annotation
cites work: A note on two problems in connexion with graphs
cites work: Improved convexity cuts for lattice point problems
cites work: The shortest path problem with two objective functions
cites work: The shortest route problem with constraints
cites work: On a multicriteria shortest path problem
cites work: Computational experience with an algorithm for finding the k shortest paths in a network
cites work: Solving k-shortest and constrained shortest path problems efficiently
full work available at URL: 0377-2217(92)90060-m
OpenAlex ID: W2022506245
description: scientific article; zbMATH DE number 149249