Showing cs.DSShow all
2 papers · 1 filter
cs.DS2023
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…
cs.DS2023
An Improved Approximation Algorithm for the Max--Section Problem
Dor Katzelnick, Aditya Pillai, Roy Schwartz +1
We consider the Max--Section problem, where we are given an undirected graph equipped with non-negative edge weights and the goal is to…