skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

Fast Algorithms for Join Operations on Tree Decompositions

van Rooij, J.M.M Fomin, F.V ; Sub Algorithms and Complexity ; Algorithms and Complexity ; Kratsch, S ; van Leeuwen, Erik Jan

2020

Texto completo disponível

Citações Citado por
  • Título:
    Fast Algorithms for Join Operations on Tree Decompositions
  • Autor: van Rooij, J.M.M
  • Fomin, F.V ; Sub Algorithms and Complexity ; Algorithms and Complexity ; Kratsch, S ; van Leeuwen, Erik Jan
  • Assuntos: Dynamic Programming ; Fast Fourier Tran ; Fast Subset Convolution ; Möbius transform ; Sigma-Rho Domination ; Taverne ; Tree decompositions
  • Notas: https://dspace.library.uu.nl/handle/1874/414753
    0302-9743
    12160, 262-297 (2020)
  • Descrição: Treewidth is a measure of how tree-like a graph is. It has many important algorithmic applications because many NP-hard problems on general graphs become tractable when restricted to graphs of bounded treewidth. Algorithms for problems on graphs of bounded treewidth mostly are dynamic programming algorithms using the structure of a tree decomposition of the graph. The bottleneck in the worst-case run time of these algorithms often is the computations for the so called join nodes in the associated nice tree decomposition. In this paper, we review two different approaches that have appeared in the literature about computations for the join nodes: one using fast zeta and Möbius transforms and one using fast Fourier transforms. We combine these approaches to obtain new, faster algorithms for a broad class of vertex subset problems known as the [σ,ρ] -domination problems. Our main result is that we show how to solve [σ,ρ]-domination problems in O(st+2tn2(tlog(s)+log(n))) arithmetic operations. Here, t is the treewidth, s is the (fixed) number of states required to represent partial solutions of the specific [σ,ρ]-domination problem, and n is the number of vertices in the graph. This reduces the polynomial factors involved compared to the previously best time bound (van Rooij, Bodlaender, Rossmanith, ESA 2009) of O(st+2(st)2(s−2)n3) arithmetic operations. In particular, this removes the dependence of the degree of the polynomial on the fixed number of states s.
  • Data de criação/publicação: 2020
  • Idioma: Inglês
Links
Voltar para lista de resultados
Resultado  1

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.