What is the best exact algorithm to compute the core of a graph?
Computing the core of a graph is hard: even deciding if a given 3-colourable graph is a core is co-NP-complete, see Hell and Nesetril.  There are settings where core computation can be done efficiently, see Efficient Core Computation in Data Exchange by Georg Gottlob and Alan Nash for a database setting; here some reasonable restrictions on the kinds of constraints in the database schema allow cores to be computed efficiently.

Edit: Other than the Gottlob/Nash work mentioned above, I am not aware of any other attempts to provide efficient algorithms for core computation.  Pointers to any algorithms better than brute force (exact or otherwise) would be welcome.