The DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.
Resource Constrained Shortest Paths
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“knowing that the resource-constrained shortest path problem is NP-hard even with one resource (Mehlhorn and Ziegelmann, 2000).”
From Scheduling multiple agile Earth observation satellites with multiple observations (2026) · cites this paper as Mehlhorn and Ziegelmann, 2000
In the citing paper
“The worst-case complexity of Algorithm 1 is exponential”
From Scheduling multiple agile Earth observation satellites with multiple observations (2026) · cites this paper as Mehlhorn and Ziegelmann, 2000
Citations
Cites
Eppstein, D. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539795290477 · Cited by 1,381
The LEDA platform for combinatorial and geometric computing
Mehlhorn, K., Näher, S., & Uhrig, C. (1997) · Lecture Notes in Computer Science · doi:10.1007/3-540-63165-8_161 · Cited by 1,199
Self-citationApproximation Schemes for the Restricted Shortest Path Problem
Hassin, R. (1992) · Mathematics of Operations Research · doi:10.1287/moor.17.1.36 · Cited by 557
Hansen, P. (1980) · Lecture Notes in Economics and Mathematical Systems · doi:10.1007/978-3-642-48782-8_9 · Cited by 525
A dual algorithm for the constrained shortest path problem
Handler, G. Y., & Zang, I. (1980) · Networks · doi:10.1002/net.3230100403 · Cited by 457
Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
Warburton, A. R. (1987) · Operations Research · doi:10.1287/opre.35.1.70 · Cited by 328
An algorithm for the resource constrained shortest path problem
Beasley, J. E., & Christofides, N. (1989) · Networks · doi:10.1002/net.3230190402 · Cited by 327
The network inhibition problem
Phillips, C. A. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167286 · Cited by 236
The shortest route problem with constraints
Joksch, H. C. (1966) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(66)90020-5 · Cited by 214
Cook, W. J., Cunningham, W. H., Pulleyblank, W. R., & Schrijver, A. (1997) · Wiley eBooks · doi:10.1002/9781118033142 · Cited by 203
Research works printed but not linked: 1
- V. Jiminez and A. Marzal. Computing the k shortest paths. A new algorithm and an experimental comparison. In Proc. 3rd Workshop on Algorithm Engineering (WAE99), LNCS 1668, pages 25–29, 1999.
Cited by
Items 101–125 of 125
An Experimental Study of Random Knapsack Problems
Beier, R., & Vöcking, B. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30140-0_55 · Cited by 1
Range, T. M. (2013) · SSRN Electronic Journal · doi:10.2139/ssrn.2340997 · Cited by 1
Optimal Path Queries in Very Large Spatial Databases
Zhang, J. (2005) · UWSpace (University of Waterloo) · Cited by 1
Energy-efficient Routing of Hybrid VehiclesPreprint
Schwan, C., & Strehler, M. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1601.02371 · Cited by 1
Robust Optimization for Airline Scheduling and Vehicle Routing
Lu, D. R. (2014) · UWSpace (University of Waterloo) · Cited by 1
Richard, O. (2007) · Cited by 1
Caminhos mínimos com recursos limitados
Uchoa, J. S. (2012) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/d.45.2012.tde-14012013-165742
der Naturwissenschaften, D. (2009)
GIS Based RouteGuidingSystemforOptimal Path PlanninginDisaster/Crisis Management
Chandio, A., MuhammadMemon, N., & Khawaja, A. (2006)
Design of Resilient Heterogeneous Wireless Networks
Kabadurmuş, Ö. (2013)
Optimisation of large scale network problems
Grigoleit, M. T. (2008) · eSpace (Curtin University)
Efficient index structures for reachability and shortest path queries
Wang, S. (2016) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/68898
Two FPTAS for the Constrained Shortest Path Problem Applied to Hybrid Vehicle Routing
Schwan, C., & Strehler, M. (2017) · Springer eBooks · doi:10.1007/978-3-319-67168-0_18
The Algorithm for Constrained Shortest Path Problem Based on Incremental Lagrangian Dual Solution
Novikov, B., & Guralnik, R. (2018) · Communications in computer and information science · doi:10.1007/978-3-319-97571-9_28
A flexible space-time tradeoff on hybrid index with bicriteria optimization
Song, X., Yang, Y., & Yu, J. (2018) · Tsinghua Science & Technology · doi:10.26599/tst.2018.9010041
Optimal Routing in Multi-Service Networks
Александрович, С. А., & Bykova, V. (2018) · International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon) · doi:10.1109/fareastcon.2018.8602436
Algorithm for optimal routing in multiservice networks
Александрович, С. А. (2018) · Prikladnaya diskretnaya matematika Prilozhenie · doi:10.17223/2226308x/11/38
On Accuracy of Approximation for the Resource Constrained Shortest Path Problem
Александрович, С. А. (2019) · Journal of Siberian Federal University Mathematics & Physics · doi:10.17516/1997-1397-2019-12-5-621-627
An Efficient Algorithm for Finding Sets of Optimal RoutesPreprint
Zoref, I., & Orda, A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.10406
Linear and Convex Programming Based Algorithms for Network Design
Shen, X. (2019) · Deep Blue (University of Michigan)
Dynamic transport mode estimation subject to joint decisions and spatio-temporal variationsPreprint
Gkiotsalitis, K. (2019) · doi:10.31224/osf.io/9y65h
Scheduling Problems in the Service Industry: Theory and Applications
van Staereling, I. V. H. (2023) · doi:10.5463/thesis.196
Efficient Short-Term Hydropower Scheduling via Resource-Constrained Shortest Paths
Monteiro, L., Tremblay, H., & Séguin, S. (2026) · International Conference on the European Energy Market (EEM) · doi:10.1109/eem68581.2026.11589703
Metadata
- Authors
- Mehlhorn, K., & Ziegelmann, M.
- Affiliations
- Max Planck Society (DE)
- ORCID
- Mehlhorn, Kurt
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2000
- Pages
- 326-337
- ISSN
- 0302-9743 (ISSN-L)
- OpenAlex
- W1491580860
- Cited by
- 124
- References
- 15
- Citations by year
- 2026: 1 · 2025: 1 · 2024: 4 · 2023: 3 · 2022: 2 · 2021: 4 · 2020: 4 · 2019: 8 · 2018: 6 · 2017: 5 · 2016: 6 · 2015: 7 · 2014: 7 · 2013: 7 · 2012: 7
- FWCI
- 1.84
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- Lecture notes in computer science (publishedVersion)
- Max Planck Institute for Plasma Physics (submittedVersion)
- MPG.PuRe (Max Planck Society) (submittedVersion)
- Untitled Event
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Social Sciences › Decision Sciences › Management Science and Operations Research › Resource-Constrained Project Scheduling
- Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Vehicle Routing Optimization Methods
- Keywords
- resource constraints, linear programming relaxation, combinatorial algorithms, polynomial-time algorithms, exact algorithms, approximation algorithms, NP-completeness
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.