News for hackers. Stuff that matters.

A comment on Ant Colony Optimization Algorithms. Parent comment

Re:Ant Colony Optimization Algorithms by patmcguire on Sunday May 04, 2014 @12:23PM (#7694776)
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?

[ Parent | on HN ]
Re:Ant Colony Optimization Algorithms by mvanotti on Sunday May 04, 2014 @12:38PM (#7694833)
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.
[ Parent | on HN ]