2 papers
cs.DS2025
Sampling Unlabeled Chordal Graphs in Expected Polynomial Time
Úrsula Hébert-Johnson, Daniel Lokshtanov
We design an algorithm that generates an -vertex unlabeled chordal graph uniformly at random in expected polynomial time. Along the way, we develop the following two results: (1…
cs.DS2023
Counting and Sampling Labeled Chordal Graphs in Polynomial Time
Ursula Hebert-Johnson, Daniel Lokshtanov, Eric Vigoda
We present the first polynomial-time algorithm to exactly compute the number of labeled chordal graphs on vertices. Our algorithm solves a more general problem: given and $…