The Densest k Subgraph Problem in b-Outerplanar Graphs

Sean Gonzales, Theresa Migler

We give an exact $O(n{k}^2)$ algorithm for finding the densest k subgraph in outerplanar graphs. We extend this to an exact $O(n{k}^2{8}^b)$ algorithm for finding the densest k subgraph…