Garbage trucks have to visit every edge (street segment) once, not every vertex ... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

patmcguire on May 4, 2014 | parent | context | favorite | on: Ant Colony Optimization Algorithms

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

Or is the process to make a non-Eulerian graph Eulerian NP?

mvanotti on May 4, 2014 [–]

Once 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.

Consider applying for YC's Fall 2026 batch! Applications are open till July 27.
Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact