Paper Info
Title
On listing, sampling, and counting the chordal graphs with edge constraints
Abstract
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 that at least one of the input graphs 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 indicate 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.
Year
DOI
Venue
2010
10.1016/j.tcs.2010.03.024
Theoretical Computer Science
Keywords
Field
DocType
P-completeness result,Chordal completion/deletion,natural generalization,Enumeration,Markov chain Monte Carlo,natural Markov chain,edge constraint,chordal completion,polynomial space,sampling problem,#P-completeness,polynomial time,Graph sandwich,chordal graph,random sampling,listing problem
Discrete mathematics,Indifference graph,Combinatorics,Interval graph,Computer science,Markov chain,Chordal graph,Counting problem,PSPACE,Sampling (statistics),Time complexity
Journal
Volume
Issue
ISSN
411
26-28
Theoretical Computer Science
Citations 
PageRank 
References 
3
0.41
23
Authors
4
Name
Order
Citations
PageRank
Shuji Kijima118123.04
Masashi Kiyomi220417.45
Yoshio Okamoto317028.50
Takeaki Uno41319107.99