Markus L. Schmid

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number

Abstract We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that comput...