On Approximating Cutwidth and Pathwidth
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916202107895808 |
|---|---|
| author | Bansal, Nikhil Katzelnick, Dor Schwartz, Roy |
| author_facet | Bansal, Nikhil Katzelnick, Dor Schwartz, Roy |
| contents | 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 edges crossing any point is minimized. We give a $ \log^{1+o(1)}(n)$ approximation for the problem, substantially improving upon the previous poly-logarithmic guarantees based on the standard recursive balanced partitioning approach of Leighton and Rao (FOCS'88). Our key idea is a new metric decomposition procedure that is suitable for handling min-max objectives, which could be of independent interest. We also use this to show other results, including an improved $ \log^{1+o(1)}(n)$ approximation for computing the pathwidth of a graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_15639 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On Approximating Cutwidth and Pathwidth Bansal, Nikhil Katzelnick, Dor Schwartz, Roy Data Structures and Algorithms 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 edges crossing any point is minimized. We give a $ \log^{1+o(1)}(n)$ approximation for the problem, substantially improving upon the previous poly-logarithmic guarantees based on the standard recursive balanced partitioning approach of Leighton and Rao (FOCS'88). Our key idea is a new metric decomposition procedure that is suitable for handling min-max objectives, which could be of independent interest. We also use this to show other results, including an improved $ \log^{1+o(1)}(n)$ approximation for computing the pathwidth of a graph. |
| title | On Approximating Cutwidth and Pathwidth |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2311.15639 |