Parameterized dynamic data structure for Split Completion
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929242728562688 |
|---|---|
| author | Majewski, Konrad Pilipczuk, Michał Zych-Pawlewicz, Anna |
| author_facet | Majewski, Konrad Pilipczuk, Michał Zych-Pawlewicz, Anna |
| contents | We design a randomized data structure that, for a fully dynamic graph $G$ updated by edge insertions and deletions and integers $k, d$ fixed upon initialization, maintains the answer to the Split Completion problem: whether one can add $k$ edges to $G$ to obtain a split graph. The data structure can be initialized on an edgeless $n$-vertex graph in time $n \cdot (k d \cdot \log n)^{\mathcal{O}(1)}$, and the amortized time complexity of an update is $5^k \cdot (k d \cdot \log n)^{\mathcal{O}(1)}$. The answer provided by the data structure is correct with probability $1-\mathcal{O}(n^{-d})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08816 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parameterized dynamic data structure for Split Completion Majewski, Konrad Pilipczuk, Michał Zych-Pawlewicz, Anna Data Structures and Algorithms We design a randomized data structure that, for a fully dynamic graph $G$ updated by edge insertions and deletions and integers $k, d$ fixed upon initialization, maintains the answer to the Split Completion problem: whether one can add $k$ edges to $G$ to obtain a split graph. The data structure can be initialized on an edgeless $n$-vertex graph in time $n \cdot (k d \cdot \log n)^{\mathcal{O}(1)}$, and the amortized time complexity of an update is $5^k \cdot (k d \cdot \log n)^{\mathcal{O}(1)}$. The answer provided by the data structure is correct with probability $1-\mathcal{O}(n^{-d})$. |
| title | Parameterized dynamic data structure for Split Completion |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.08816 |