Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



COMPUTATIONAL COMPLEXITY OF BIASED DIFFUSION-LIMITED AGGREGATION
Indexado
WoS WOS:000778502000037
Scopus SCOPUS_ID:85130586339
DOI 10.1137/18M1215815
Año 2022
Tipo artículo de investigación

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



Diffusion-Limited Aggregation (DLA) is a cluster-growth model that consists in a set of particles that are sequentially aggregated over a two-dimensional grid. In this paper, we introduce a biased version of the DLA model, in which particles are limited to move in a subset of possible directions. We denote by k-DLA the model where the particles move only in k possible directions. We study the biased DLA model from the perspective of Computational Complexity, defining two decision problems The first problem is Prediction, whose input is a site of the grid c and a sequence S of walks, representing the trajectories of a set of particles. The question is whether a particle stops at site c when sequence S is realized. The second problem is Realization, where the input is a set of positions of the grid, P. The question is whether there exists a sequence S that realizes P, i.e. all particles of S exactly occupy the positions in P. Our aim is to classify the Prediciton and Realization problems for the different versions of DLA. We first show that Prediction is P-Complete for 2-DLA (thus for 3-DLA). Later, we show that Prediction can be solved much more efficiently for 1-DLA. In fact, we show that in that case the problem is NL-Complete. With respect to Realization, we show that restricted to 2-DLA the problem is in P, while in the 1-DLA case, the problem is in L.

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Mathematics
Mathematics, Applied
Scopus
Sin Disciplinas
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 Bitar, Nicolas Hombre Universidad de Chile - Chile
2 GOLES-CHACC, ERIC ANTONIO Hombre Universidad Adolfo Ibáñez - Chile
Universidad Adolfo Ibá Ñez - Chile
3 Montealegre, Pedro Hombre Universidad Adolfo Ibáñez - Chile
Universidad Adolfo Ibá Ñez - Chile

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
FONDECYT
CONICYT-PFCHA
Fondo Nacional de Desarrollo Científico y Tecnológico
CONICYT-PFCHA/MagisterNacional/2019
Agencia Nacional de Investigación y Desarrollo
ANID via PAI + Convocatoria Nacional Subvencion a la Incorporacion en la Academia Ano 2017
Mag\

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
The first author was partially supported by CONICYT-PFCHA/MagisterNacional/2019 -22190497. The second and third authors were partially supported by FONDECYT 1200006. The third author was also partially supported by ANID via PAI + Convocatoria Nacional Subvencion a la Incorporacion en la Academia Ano 2017 + PAI77170068 and by FONDECYT 11190482.
\ast Received by the editors September 21, 2018; accepted for publication (in revised form) December 12, 2021; published electronically March 31, 2022. https://doi.org/10.1137/18M1215815 \bfF \bfu \bfn \bfd \bfi \bfn \bfg : The first author was partially supported by CONICYT-PFCHA/Mag\{\'i}sterNacional/ 2019 - 22190497. The second and third authors were partially supported by FONDECYT 1200006. The third author was also partially supported by ANID via PAI + Convocatoria Nacional Subvencio\'n a la Incorporacio\'n en la Academia An\~o 2017 + PAI77170068 and by FONDECYT 11190482. \dagger Departamento de Ingenier\{\i'}a Matem\a'tica, Universidad de Chile, Santiago, Chile (nbitar@dim. uchile.cl). \ddagger Facultad de Ingenier\{\'i}a y Ciencias, Universidad Adolfo Ib\a'n\~ez, Santiago, Chile (eric.chacc@uai.cl, p.montealegre@uai.cl).

Muestra la fuente de financiamiento declarada en la publicación.