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)\cdot n^{\mathcal{O}(1)}\) and use \(g(k)\cdot (\log n)^{\mathcal{O}(1)}\) 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 \(n^{O(1)}\) 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 develop different ways to tackle them.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Space Efficient Algorithms for Parameterised Problems

  • Sheikh Shakil Akhtar,
  • Pranabendu Misra,
  • Geevarghese Philip

摘要

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)\cdot n^{\mathcal{O}(1)}\) and use \(g(k)\cdot (\log n)^{\mathcal{O}(1)}\) 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 \(n^{O(1)}\) 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 develop different ways to tackle them.