Local 2-separators
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909100715016192 |
|---|---|
| author | Carmesin, Johannes |
| author_facet | Carmesin, Johannes |
| contents | How can sparse graph theory be extended to large networks, where algorithms whose running time is estimated using the number of vertices are not good enough? I address this question by introducing 'Local Separators' of graphs. Applications include:
1. A unique decomposition theorem for graphs along their local 2-separators analogous to the 2-separator theorem;
2. an exact characterisation of graphs with no bounded subdivision of a wheel. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2008_03032 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Local 2-separators Carmesin, Johannes Combinatorics 05C40, 05C83, 05C90, 05C75, 05C85, 05C82 How can sparse graph theory be extended to large networks, where algorithms whose running time is estimated using the number of vertices are not good enough? I address this question by introducing 'Local Separators' of graphs. Applications include: 1. A unique decomposition theorem for graphs along their local 2-separators analogous to the 2-separator theorem; 2. an exact characterisation of graphs with no bounded subdivision of a wheel. |
| title | Local 2-separators |
| topic | Combinatorics 05C40, 05C83, 05C90, 05C75, 05C85, 05C82 |
| url | https://arxiv.org/abs/2008.03032 |