Name
Title | ||
|---|---|---|
Approximation algorithms for solving the constrained arc routing problem in mixed graphs. |
Abstract | ||
|---|---|---|
•We consider the constrained arc routing problem in mixed graphs.•It is to determine a shortest tour T traversing each e between l(e) and u(e) times.•We design an (1+1/l_0)-approximation algorithm in O(n2m3logn) to solve this problem.•We also present two optimal algorithms to solve its special versions, respectively. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.ejor.2014.04.039 | European Journal of Operational Research |
Keywords | Field | DocType |
Combinatorial optimization,Arc routing,Lower/upper demand bound,Approximation algorithm,Combinatorial algorithm | Integer,Arc routing,Approximation algorithm,Discrete mathematics,Combinatorics,Mathematical optimization,Rational number,Vertex (geometry),Route inspection problem,Mixed graph,Length function,Mathematics | Journal |
Volume | Issue | ISSN |
239 | 1 | 0377-2217 |
Citations | PageRank | References |
2 | 0.35 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Honglin Ding | 1 | 4 | 0.75 |
| Jianping Li | 2 | 455 | 76.28 |
| Ko-wei Lih | 3 | 529 | 58.80 |