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

  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.