xkcd mentions the faster-than-factorial dynamic programming solution to the traveling salesman problem!
( Read more... )
( Read more... )
11 comments | Leave a comment
0xDE
12 June 2006 @ 10:26 pm
An st-orientation of an undirected graph is an assignment of a direction for each edge, turning it into a directed acyclic graph with one source and one sink. For any biconnected graph such an orientation may be found in linear time via depth first search: For each DFS tree edge (u,v) (where u is the parent), orient (u,v) oppositely to the DFS tree edge down from the low vertex of v into the subtree containing u and v. For each nontree edge (u,v) (where u is the top vertex), orient (u,v) the same as the DFS tree edge down from u into the subtree containing v. I've been meaning to add this to PADS for a while, after lecturing on it as part of the graph drawing section of my undergraduate graph algorithms class this quarter, but it's now there (in Biconnectivity.py) after I found motivation in a connection to xyz graph recognition:
Any biconnected 3-regular graph can be partitioned in at most 2n/2-1 different ways into three matchings. The idea of the proof is to process the vertices in a topological ordering (also added to PADS, in TopologicalOrder.py) of an st-orientation, and when processing each vertex choose how to assign the adjacent edges to the three matchings, consistently with prior choices. We only have to make a binary choice at the n/2-1 vertices with one incoming and two outgoing edges; at all other vertices there is no choice to be made. This leads to an O(n 2n/2) time algorithm for recognizing xyz graphs, which I implemented as part of PADS in xyzGraph.py.
( Read more... )
Any biconnected 3-regular graph can be partitioned in at most 2n/2-1 different ways into three matchings. The idea of the proof is to process the vertices in a topological ordering (also added to PADS, in TopologicalOrder.py) of an st-orientation, and when processing each vertex choose how to assign the adjacent edges to the three matchings, consistently with prior choices. We only have to make a binary choice at the n/2-1 vertices with one incoming and two outgoing edges; at all other vertices there is no choice to be made. This leads to an O(n 2n/2) time algorithm for recognizing xyz graphs, which I implemented as part of PADS in xyzGraph.py.
( Read more... )
06 March 2006 @ 05:29 pm
More mathematics in which I'm undereducated: local central limit theorems. That is, if we add together a bunch of independent identically distributed random variables, the central limit theorem tells us the distribution of the sum will look Gaussian on a large scale. A local central limit theorem will tell us that the distribution will look Gaussian on a small scale, in small neighborhoods.
( Read more... )