Paper Info
Title
Approximation Algorithms for a Mixed Postman Problem with Restrictions on the Arcs
Abstract
The mixed postman problem consists of finding a minimum cost tour of a mixed graph traversing all its vertices, edges, and arcs at least once. We consider an NP-hard variant of the mixed postman problem where all arcs must be traversed exactly once, known as the edges postman problem. We present four approximation algorithms for the edges postman problem with different guarantees. Our main result is a 4/3-approximation algorithm for the edges postman problem.
Year
DOI
Venue
2015
10.1007/978-3-319-44003-3_5
Studies in Computational Intelligence
Keywords
DocType
Volume
Mixed graph,Postman problem,Approximation algorithm
Conference
663
ISSN
Citations 
PageRank 
1860-949X
0
0.34
References 
Authors
0
1
Name
Order
Citations
PageRank
Francisco Javier Zaragoza Martínez153.91