# The complexity of the travelling repairman problem

Foto Afrati; Stavros Cosmadakis; Christos H. Papadimitriou; George Papageorgiou; Nadia Papakostantinou

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1986)

- Volume: 20, Issue: 1, page 79-87
- ISSN: 0988-3754

## Access Full Article

top## How to cite

topAfrati, Foto, et al. "The complexity of the travelling repairman problem." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 20.1 (1986): 79-87. <http://eudml.org/doc/92248>.

@article{Afrati1986,

author = {Afrati, Foto, Cosmadakis, Stavros, Papadimitriou, Christos H., Papageorgiou, George, Papakostantinou, Nadia},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {mean-flow variant of the travelling salesman problem; polynomial-time algorithm; NP-complete},

language = {eng},

number = {1},

pages = {79-87},

publisher = {EDP-Sciences},

title = {The complexity of the travelling repairman problem},

url = {http://eudml.org/doc/92248},

volume = {20},

year = {1986},

}

TY - JOUR

AU - Afrati, Foto

AU - Cosmadakis, Stavros

AU - Papadimitriou, Christos H.

AU - Papageorgiou, George

AU - Papakostantinou, Nadia

TI - The complexity of the travelling repairman problem

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 1986

PB - EDP-Sciences

VL - 20

IS - 1

SP - 79

EP - 87

LA - eng

KW - mean-flow variant of the travelling salesman problem; polynomial-time algorithm; NP-complete

UR - http://eudml.org/doc/92248

ER -

## References

top- 1. M. R. GAREY and D. S. JOHNSON, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and co., San Francisco, 1979. Zbl0411.68039MR519066
- 2. S. SAHNI and T. GONZALES, P-Complete Approximation Problems, J. Assoc. Comput. Mach., Vol. 23, 1976, pp. 555-565. Zbl0348.90152MR408313

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.