Name
Abstract | ||
|---|---|---|
Given a graph (,) with a cost (or benefit) and a delay on each arc, the constrained routing problem (CRP) aims to find a minimum-cost or a maximum-benefit path from a given source to a given destination node, subject to an end-to-end delay constraint. The problem (with a single constraint) is NP-hard, and has been studied by many researchers who found fully polynomial approximation schemes (FPAS) for this problem. The current paper focuses on a generalized CRP version, CRP with hop-wise constraints (CRPH). In the generalized version, instead of one constraint there are up to −1 special-type constraints, where is the number of nodes. An FPAS based on interval partitioning is proposed for both the minimization and the maximization versions of CRPH. For (,) with nodes and arcs, the complexity of the algorithm is O( /). |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s10479-013-1308-5 | Annals OR |
Keywords | Field | DocType |
Approximation algorithms,Combinatorial problems,Shortest path,Routing | Graph,Approximation algorithm,Discrete mathematics,Mathematical optimization,Polynomial,Shortest path problem,Minification,Hop (networking),Maximization,Mathematics | Journal |
Volume | Issue | ISSN |
222 | 1 | 0254-5330 |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amir Elalouf | 1 | 0 | 1.01 |