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 Search
Busca Geral
Busca Geral
Acervo Físico
Acervo Físico
Produção Intelectual da USP
Produção USP
Search For:
Clear Search Box
Search in:
Busca Geral
Or hit Enter to replace search target
Or select another collection:
Search in:
Busca Geral
Busca Avançada
Busca por Índices
This feature requires javascript
This feature requires javascript
Multivariate Analysis of Orthogonal Range Searching and Graph Distances
Bringmann, Karl ; Husfeldt, Thore ; Magnusson, Måns
Algorithmica, 2020-08, Vol.82 (8), p.2292-2315
[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:
Multivariate Analysis of Orthogonal Range Searching and Graph Distances
Autor:
Bringmann, Karl
;
Husfeldt, Thore
;
Magnusson, Måns
Assuntos:
Algorithm Analysis and Problem Complexity
;
Algorithms
;
Computer Science
;
Computer Systems Organization and Communication Networks
;
Data Structures and Information Theory
;
Diameter
;
Diameters
;
Discrete Mathematics
;
Diskret matematik
;
IPEC 2018
;
Matematik
;
Mathematics
;
Mathematics of Computing
;
Multivariate analysis
;
Natural Sciences
;
Naturvetenskap
;
Orthogonal range searching
;
Parameterization
;
Polynomials
;
Radius
;
Searching
;
Special Issue on Parameterized and Exact Computation
;
Theory of Computation
;
Treewidth
;
Vertex cover number
;
Wiener index
É parte de:
Algorithmica, 2020-08, Vol.82 (8), p.2292-2315
Descrição:
We show that the eccentricities, diameter, radius, and Wiener index of an undirected n -vertex graph with nonnegative edge lengths can be computed in time O ( n · k + ⌈ log n ⌉ k · 2 k log n ) , where k is linear in the treewidth of the graph. For every ε > 0 , this bound is n 1 + ε exp O ( k ) , which matches a hardness result of Abboud et al. (in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016. https://doi.org/10.1137/1.9781611974331.ch28 ) and closes an open problem in the multivariate analysis of polynomial-time computation. To this end, we show that the analysis of an algorithm of Cabello and Knauer (Comput Geom 42:815–824, 2009. https://doi.org/10.1016/j.comgeo.2009.02.001 ) in the regime of non-constant treewidth can be improved by revisiting the analysis of orthogonal range searching, improving bounds of the form log d n to d + ⌈ log n ⌉ d , as originally observed by Monier (J Algorithms 1:60–74, 1980. https://doi.org/10.1016/0196-6774(80)90005-X ). We also investigate the parameterization by vertex cover number.
Editor:
New York: Springer US
Idioma:
Inglês
Links
View record from Swedish Publication Index
This feature requires javascript
This feature requires javascript
Voltar para lista de resultados
This feature requires javascript
This feature requires javascript
Buscando em bases de dados remotas. Favor aguardar.
Buscando por
em
scope:(USP_VIDEOS),scope:("PRIMO"),scope:(USP_FISICO),scope:(USP_EREVISTAS),scope:(USP),scope:(USP_EBOOKS),scope:(USP_PRODUCAO),primo_central_multiple_fe
Mostrar o que foi encontrado até o momento
This feature requires javascript
This feature requires javascript