SCIENCE@home

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

Katrin Casel,Joel D. Day,Pamela Fleischmann,Tomasz Kociumaka,F. Manea,Markus L. Schmid

Published 2019 in International Colloquium on Automata, Languages and Programming

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 computing the locality number is NP-hard but fixed parameter tractable (when the locality number or the alphabet size is treated as a parameter), and can be approximated with ratio $O(\sqrt{\log{opt}} \log n)$. As a by-product, we also relate cutwidth via the locality number to pathwidth, which is of independent interest, since it improves the currently best known approximation algorithm for cutwidth. In addition to these main results, we also consider the possibility of greedy-based approximation algorithms for the locality number.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-52 of 52 references · Page 1 of 1

CITED BY

Showing 1-10 of 10 citing papers · Page 1 of 1