Space Efficient Algorithms for Parameterised Problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912765225992192 |
|---|---|
| author | Akhtar, Sheikh Shakil Misra, Pranabendu Philip, Geevarghese |
| author_facet | Akhtar, Sheikh Shakil Misra, Pranabendu Philip, Geevarghese |
| contents | We study "space efficient" FPT algorithms for graph problems with limited memory. Let n be the size of the input graph and k be the parameter. We present algorithms that run in time f(k)*poly(n) and use g(k)*polylog(n) working space, where f and g are functions of k alone, for k-Path, MaxLeaf SubTree and Multicut in Trees. These algorithms are motivated by big-data settings where very large problem instances must be solved, and using poly(n) memory is prohibitively expensive. They are also theoretically interesting, since most of the standard methods tools, such as deleting a large set of vertices or edges, are unavailable, and we must a develop different way to tackle them. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_13342 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Space Efficient Algorithms for Parameterised Problems Akhtar, Sheikh Shakil Misra, Pranabendu Philip, Geevarghese Data Structures and Algorithms Computational Complexity Discrete Mathematics Combinatorics We study "space efficient" FPT algorithms for graph problems with limited memory. Let n be the size of the input graph and k be the parameter. We present algorithms that run in time f(k)*poly(n) and use g(k)*polylog(n) working space, where f and g are functions of k alone, for k-Path, MaxLeaf SubTree and Multicut in Trees. These algorithms are motivated by big-data settings where very large problem instances must be solved, and using poly(n) memory is prohibitively expensive. They are also theoretically interesting, since most of the standard methods tools, such as deleting a large set of vertices or edges, are unavailable, and we must a develop different way to tackle them. |
| title | Space Efficient Algorithms for Parameterised Problems |
| topic | Data Structures and Algorithms Computational Complexity Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2512.13342 |