Whoa, this is huge! I love the explanation too. The low-diameter decomposition part was very interesting. This is one of the things I love about graph theory- there are so many solved and nearly-solved problems and concepts that might be useful to each other. It's like a problem set that comes with its own toolbox to tinker with.
I was expecting something simpler tbh, but it still looks like a decent undergrad could implement it without too much trouble, even without a supplementary writeup.
Does this give any insight into the Traveling Salesman problem? The salesman would with some probability make some bigger sales on some cities while less so in other cities.
I think this gives a good more realistic viewpoint on all these graph-traversal problems. Of course the only reason to traverse any graph in some way would be if there is some benefit meaning negative cost for traversing it.
6 comments
[ 2.5 ms ] story [ 29.4 ms ] threadAn interesting read!
I was expecting something simpler tbh, but it still looks like a decent undergrad could implement it without too much trouble, even without a supplementary writeup.
I think this gives a good more realistic viewpoint on all these graph-traversal problems. Of course the only reason to traverse any graph in some way would be if there is some benefit meaning negative cost for traversing it.