On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
We discuss the problems to list, sample, and count the chordal graphs with edge constraints. The objects we look at are chordal graphs sandwiched by a given pair of graphs where we assume at least one of the input pair is chordal. The setting is a natural generalization of chordal completions and deletions. For the listing problem, we give an efficient algorithm running in polynomial time per output with polynomial space. As for the sampling problem, we give two clues that seem to imply that a randoM sampling is not easy. The first clue is that we show #P-completeness results for counting problems. The second clue is that we give an instance for which a natural Markov chain suffers from an exponential mixing time. These results provide a unified viewpoint from algorithms theory to problems arising from various areas such as statistics, data mining, and numerical computation.
Shuji Kijima Masashi Kiyomi Yoshio Okamoto Takeaki Uno
Research Institute for Mathematical Sciences,Kyoto University,Kyoto, 606-8502, Japan School of Information Science, Japan Advanced Institute of Science and Technology,1-1 Asahidai,Nomi, Graduate School of Information Science and Engineering,Tokyo Institute of Technology,2-12-1-W8-88, O National Institute of Informatics,2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
458-467
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）