skip to main content
Visitante
Meu Espaço
Minha Conta
Sair
Identificação
This feature requires javascript
Tags
Revistas Eletrônicas (eJournals)
Livros Eletrônicos (eBooks)
Bases de Dados
Bibliotecas USP
Ajuda
Ajuda
Idioma:
Inglês
Espanhol
Português
This feature required javascript
This feature requires javascript
Primo Advanced Search
Busca Geral
Busca Geral
Acervo Físico
Acervo Físico
Produção Intelectual da USP
Produção USP
Primo Advanced Search Query Term
Input search text:
Show Results with:
criteria input
Qualquer
Show Results with:
Qualquer
Primo Advanced Search prefilters
Tipo de material:
criteria input
Todos os itens
Busca Geral
Busca Simples
This feature requires javascript
Explicit Linear Kernels for Packing Problems
Garnero, Valentin ; Paul, Christophe ; Sau, Ignasi ;
Thilikos
,
Dimitrios
M
.
Algorithmica, 2019-04, Vol.81 (4), p.1615-1656
[Periódico revisado por pares]
New York: Springer US
Texto completo disponível
Citações
Citado por
Exibir Online
Detalhes
Resenhas & Tags
Mais Opções
Nº de Citações
This feature requires javascript
Enviar para
Adicionar ao Meu Espaço
Remover do Meu Espaço
E-mail (máximo 30 registros por vez)
Imprimir
Link permanente
Referência
EasyBib
EndNote
RefWorks
del.icio.us
Exportar RIS
Exportar BibTeX
This feature requires javascript
Título:
Explicit Linear Kernels for Packing Problems
Autor:
Garnero, Valentin
;
Paul, Christophe
;
Sau, Ignasi
;
Thilikos
,
Dimitrios
M
.
Assuntos:
Algorithm Analysis and Problem Complexity
;
Algorithms
;
Apexes
;
Computer Science
;
Computer Systems Organization and Communication Networks
;
Data Structures and Algorithms
;
Data Structures and Information Theory
;
Discrete Mathematics
;
Graph theory
;
Graphs
;
Kernels
;
Mathematics of Computing
;
Theory of Computation
É parte de:
Algorithmica, 2019-04, Vol.81 (4), p.1615-1656
Descrição:
During the last years, several algorithmic meta-theorems have appeared (Bodlaender et al. [FOCS 2009], Fomin et al. [SODA 2010], Kim et al. [ICALP 2013]) guaranteeing the existence of linear kernels on sparse graphs for problems satisfying some generic conditions. The drawback of such general results is that it is usually not clear how to derive from them constructive kernels with reasonably low explicit constants. To fill this gap, we recently presented [STACS 2014] a framework to obtain explicit linear kernels for some families of problems whose solutions can be certified by a subset of vertices . In this article we enhance our framework to deal with packing problems, that is, problems whose solutions can be certified by collections of subgraphs of the input graph satisfying certain properties. F - Packing is a typical example: for a family F of connected graphs that we assume to contain at least one planar graph, the task is to decide whether a graph G contains k vertex-disjoint subgraphs such that each of them contains a graph in F as a minor. We provide explicit linear kernels on sparse graphs for the following two orthogonal generalizations of F - Packing : for an integer ℓ ⩾ 1 , one aims at finding either minor-models that are pairwise at distance at least ℓ in G ( ℓ - F -Packing ), or such that each vertex in G belongs to at most ℓ minors-models ( F -Packing with ℓ -Membership ). Finally, we also provide linear kernels for the versions of these problems where one wants to pack subgraphs instead of minors.
Editor:
New York: Springer US
Idioma:
Inglês
Links
View record in HAL
This feature requires javascript
This feature requires javascript
Voltar para lista de resultados
Anterior
Resultado
9
Avançar
This feature requires javascript
This feature requires javascript
Buscando em bases de dados remotas. Favor aguardar.
Buscando por
em
scope:(USP_PRODUCAO),scope:(USP_EBOOKS),scope:("PRIMO"),scope:(USP),scope:(USP_EREVISTAS),scope:(USP_FISICO),primo_central_multiple_fe
Mostrar o que foi encontrado até o momento
This feature requires javascript
This feature requires javascript