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.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.