3 ms·
Garbage trucks have to visit every edge (street segment) once, not every vertex (intersection) once, correct? Can you use Eulerian Paths? http://en.m.wikipedia
by patmcguire 12y ago
Garbage trucks have to visit every edge (street segment)
once, not every vertex (intersection) once, correct? Can you use Eulerian Paths?
http://en.m.wikipedia.org/wiki/Eulerian_path http://en.m.wikipedia.org/wiki/Eulerian_path
Or is the process to make a non-Eulerian graph Eulerian NP?
- mvanotti 12y agoOnce you have a mixed graph (One-way streets and two-way streets), the problem is known as the Mixed Chinese Postman Problem and is NP.