Why does the Gomory-Hu algorithm work? i.e. why does the tree that it outputs have the property that you can do min-cut by removing its smallest edge and returning the connected components? (My hunch is that Fig. 4 has the answer if I stare at it long enough)


( Read more... )

Carla P. Gomes, Ashish Sabharwal, Bart Selman - Model Counting: A New Strategy for Obtaining Good Bounds tackles the interesting problem of counting the number of assignments satisfying an instance of SAT (the instance is satisfiable if this is >0 ( Read more... )