Slashdot Mirror

← Back to Stories (view on slashdot.org)

Road Coloring Problem Solved

Posted by kdawson on from the hard-but-not-complicated dept.

ArieKremen writes "Israeli Avraham Trakhtman, a Russian immigrant mathematician who had been employed as a night watchman, has solved the Road Coloring problem. First posed in 1970 by Benjamin Weiss and Roy Adler, the problem posits that given a finite number of roads, one should be able to draw a map, coded in various colors, that leads to a certain destination regardless of the point of origin. The 63-year-old Trakhtman jotted down the solution in pencil in 8 pages. The problem has real-world implementation in message and traffic routing."

9 of 202 comments (clear)

  1. The writeup is misleading by karl+marx+is+my+hero · · Score: 5, Informative

    The guy is actually a mathematician who had to work as a security guard right after he immigrated to Israel, which is common for most immigrants. This guy had lots of formal training solving equations like this.

  2. Re:XKCD by Anonymous Coward · · Score: 5, Informative

    No, today's XKCD is about the traveling salesman problem. They are very different.

  3. Bad timing. by Rob+T+Firefly · · Score: 5, Funny

    Unfortunately for him, a cheap, safe, mass-market flying car was announced an hour later.

    --
    Slashdot Burying Stories About Slashdot Media Owned
  4. wikipedia by ZiggyM · · Score: 5, Informative

    from Wikipedia: In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. http://en.wikipedia.org/wiki/Road_Coloring_Conjecture/

    1. Re:wikipedia by Stephan202 · · Score: 5, Informative

      Drop the trailing slash: http://en.wikipedia.org/wiki/Road_Coloring_Conjecture

    2. Re:wikipedia by Jasin+Natael · · Score: 5, Informative

      The problem is more constrained than that. Think about it more like this: You're in a town that's been planned very carefully. At any intersection, the possible roads away from that intersection are labeled with colors. I'll assume three colors, and that each intersection has exactly three roads leading away from it (the number of roads that lead into the intersection doesn't matter).

      Your friend tells you that his address is "Red-Blue-Blue". This means that, no matter which intersection you start from, by repeatedly following these directions, you WILL end up at his house.

      --
      True science means that when you re-evaluate the evidence, you re-evaluate your faith.
  5. A Subquadratic Algorithm for Road Coloring by Frans+Faase · · Score: 5, Informative

    Apart from the referenced paper being some months old, the author has an extended paper with an efficient algorithm. See A Subquadratic Algorithm for Road Coloring.

  6. Old news? by amplt1337 · · Score: 5, Insightful

    1. Here's wtf the problem even is, for those of us who aren't all up in the "mathematical curiosities" business. Basically the question is, for a specific kind of graph (where you can go from point A to a finite number of points B, C, or D, etc) can you label the possible paths from each point so that, starting from anywhere, you can follow an invariable rule that will get you to a specific destination point. (Check the link, the picture makes much more sense).

    2. Apparently his proof was published last September. It's "news" because it's just now hitting the semi-mainstream press. You people fail at nerddom.

    --
    Freedom isn't free; its price is the well-being of others.
  7. Re:Night Watchman? by Yvanhoe · · Score: 5, Funny

    In Soviet Russia they say that because Americans were so poor mathematicians, they had to invent the computer...

    --
    The Wise adapts himself to the world. The Fool adapts the world to himself. Therefore, all progress depends on the Fool.