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

Neighborhood complexity and kernelization for nowhere dense classes of graphs

Eickmeyer, Kord ; Giannopoulou, Archontia C ; Kreutzer, Stephan ; O-joung, Kwon ; Pilipczuk, Michał ; Rabinovich, Roman ; Siebertz, Sebastian

arXiv.org, 2016-12

Ithaca: Cornell University Library, arXiv.org

Texto completo disponível

Citações Citado por
  • Título:
    Neighborhood complexity and kernelization for nowhere dense classes of graphs
  • Autor: Eickmeyer, Kord ; Giannopoulou, Archontia C ; Kreutzer, Stephan ; O-joung, Kwon ; Pilipczuk, Michał ; Rabinovich, Roman ; Siebertz, Sebastian
  • Assuntos: Apexes ; Complexity ; Computer Science - Discrete Mathematics ; Graph theory ; Graphs ; Intersections ; Mathematics - Combinatorics ; Parameterization
  • É parte de: arXiv.org, 2016-12
  • Descrição: We prove that whenever \(G\) is a graph from a nowhere dense graph class \(\mathcal{C}\), and \(A\) is a subset of vertices of \(G\), then the number of subsets of \(A\) that are realized as intersections of \(A\) with \(r\)-neighborhoods of vertices of \(G\) is at most \(f(r,\epsilon)\cdot |A|^{1+\epsilon}\), where \(r\) is any positive integer, \(\epsilon\) is any positive real, and \(f\) is a function that depends only on the class \(\mathcal{C}\). This yields a characterization of nowhere dense classes of graphs in terms of neighborhood complexity, which answers a question posed by Reidl et al. As an algorithmic application of the above result, we show that for every fixed \(r\), the parameterized Distance-\(r\) Dominating Set problem admits an almost linear kernel on any nowhere dense graph class. This proves a conjecture posed by Drange et al., and shows that the limit of parameterized tractability of Distance-\(r\) Dominating Set on subgraph-closed graph classes lies exactly on the boundary between nowhere denseness and somewhere denseness.
  • Editor: Ithaca: Cornell University Library, arXiv.org
  • Idioma: Inglês
Links
Voltar para lista de resultados

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

Buscando em bases de dados remotas. Favor aguardar.