David Eppstein – Publications

Publications with Denis Kurz

K-best solutions of MSO problems on tree-decomposable graphs.
D. Eppstein and D. Kurz.
arXiv:1703.02784.
Proc. 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Vienna, Austria, 2017.
Leibniz International Proceedings in Informatics (LIPIcs) 89, pp. 16.1–16.13, doi:10.4230/LIPIcs.IPEC.2017.16

We show that, on graphs of bounded treewidth, for any optimization problem definable in monadic second-order logic, we can find the k best solutions in logarithmic time per solution.