In this paper, we propose two directions which we will investigate in the future work. One is the simulated annealing method and the other is the multi-decomposition method.
Simulated annealing method is useful especially in designing efficient approximate algorithms for the problems of computing weighted combinatorial structures. Since the mixing time of the Markov chain for this kind of problems can depend on the value of the weights instead of the size of the values in binary, e.g. weighted matchings in bipartite graphs. We present some results we have for counting weighted matchings in bipartite graphs and related problems, e.g. the ice-model. We also present our experiment for solving the problem of counting weighted matchings in general graphs.
Destainville proposed the method of multi-decomposition. The advantage of multi-decomposition is that it allows us to apply the multi-decomposition recursively if the structure of the state space is in some sense symmetric. We are exploring applications of the multi-decomposition method on two problems, one is counting the number Eulerian tours in 4-regular graphs and the other is counting the forests in given graphs. Some partial results and conjectures are given.