Premium
Plowing with precedence in polynomial time
Author(s) -
Castro Campos Rodrigo A.,
Rodríguez Villalobos Cynthia A.,
Zaragoza Martínez Francisco Javier
Publication year - 2020
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21987
Subject(s) - heuristics , traverse , tree traversal , time complexity , computer science , state (computer science) , mathematical optimization , polynomial , mathematics , algorithm , geography , cartography , mathematical analysis
The plowing with precedence problem is a variant of the windy postman problem, where a plow is required to clean streets after a heavy snowfall with traversing costs depending on the direction of traversal as well as whether a street has been previously plowed or not. We prove that this problem can be solved in polynomial time under natural cost structures. We also propose heuristics for this problem, which compare favorably with the state of the art.