On Approximating Cutwidth and Pathwidth

Nikhil Bansal, Dor Katzelnick, Roy Schwartz

We study graph ordering problems with a min-max objective. A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of e…