Dataciencia

Colección SciELO Chile

Sparse Dynamic Programming on DAGs with Small Width

Indexado

WoS	WOS:000468036500014
Scopus	SCOPUS_ID:85062363208

DOI

10.1145/3301312

Año

2019

Tipo

artículo de investigación

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras

Abstract

The main ingredient of the proposed framework is a new algorithm for finding a minimum path cover of a DAG (V, E) in O(k vertical bar E vertical bar log vertical bar V vertical bar) time, improving all known time-bounds when k is small and the DAG is not too dense. In addition to boosting the sparse dynamic programming framework, an immediate consequence of this new minimum path cover algorithm is an improved space/time tradeoff for reachability queries in arbitrary directed graphs.

Revista

Revista	ISSN
Acm Transactions On Algorithms	1549-6325

Métricas Externas

PlumX	Altmetric	Dimensions

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

Plumx: https://plumanalytics.com/learn/about-metrics/
Altmetric: https://www.altmetric.com/about-altmetrics/what-are-altmetrics/
Dimensions: https://www.dimensions.ai/why-dimensions/

Disciplinas de Investigación

WOS
Mathematics, Applied
Computer Science, Theory & Methods

Scopus
Mathematics (Miscellaneous)

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	Makinen, Veli	Hombre	Univ Helsinki - Finlandia Helsingin Yliopisto - Finlandia
2	Tomescu, Alexandru I.	Hombre	Univ Helsinki - Finlandia Helsingin Yliopisto - Finlandia
3	Kuosmanen, Anna	Mujer	Univ Helsinki - Finlandia Helsingin Yliopisto - Finlandia
4	Paavilainen, Topi	Hombre	Univ Helsinki - Finlandia Helsingin Yliopisto - Finlandia
5	Gagie, Travis	Hombre	Universidad Diego Portales - Chile
6	Chikhi, Rayan	-	Univ Lille - Francia University of Lille - Francia Université de Lille - Francia

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

Financiamiento

Fuente
FONDECYT
Fondo Nacional de Desarrollo Científico, Tecnológico y de Innovación Tecnológica
Fondo Nacional de Desarrollo CientÃfico, TecnolÃ³gico y de InnovaciÃ³n TecnolÃ³gica
Academy of Finland
Futurice Oy
Futurice

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

Agradecimientos

Agradecimiento
This work was funded in part by the Academy of Finland (Grant No. 274977 to A.I.T. and Grants No. 284598 and No. 309048 to A.K. and V.M.), by Futurice Oy (to T.P.), and by Fondecyt Grant No. 1171058 (to T.G.).
This is an extended version of a conference paper [26]. This work was funded in part by the Academy of Finland (Grant No. 274977 to A.I.T. and Grants No. 284598 and No. 309048 to A.K. and V.M.), by Futurice Oy (to T.P.), and by Fondecyt Grant No. 1171058 (to T.G.). Authors’ addresses: V. Mäkinen, A. I. Tomescu, A. Kuosmanen, and T. Paavilainen, Helsinki Institute for Information Technology, Department of Computer Science, University of Helsinki, P.O. Box 68, Gustaf Hällströmin katu 2b, Helsinki, 00014, Finland; emails: {veli.makinen, alexandru.tomescu, anna.kuosmanen}@helsinki.fi; T. Gagie, EIT, Diego Portales University, Av. Ejército 441, Santiago, Chile; email: travis.gagie@gmail.com; R. Chikhi, CNRS, CRIStAL, University of Lille, Bâtiment M3 extension, Avenue Carl Gauss, Villeneuve d’Ascq Cedex, 59655, France; email: rayan.chikhi@univ-lille.fr. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. 1549-6325/2019/02-ART29 $15.00 https://doi.org/10.1145/3301312

Agradecimiento

This work was funded in part by the Academy of Finland (Grant No. 274977 to A.I.T. and Grants No. 284598 and No. 309048 to A.K. and V.M.), by Futurice Oy (to T.P.), and by Fondecyt Grant No. 1171058 (to T.G.).

This is an extended version of a conference paper [26]. This work was funded in part by the Academy of Finland (Grant No. 274977 to A.I.T. and Grants No. 284598 and No. 309048 to A.K. and V.M.), by Futurice Oy (to T.P.), and by Fondecyt Grant No. 1171058 (to T.G.). Authors’ addresses: V. Mäkinen, A. I. Tomescu, A. Kuosmanen, and T. Paavilainen, Helsinki Institute for Information Technology, Department of Computer Science, University of Helsinki, P.O. Box 68, Gustaf Hällströmin katu 2b, Helsinki, 00014, Finland; emails: {veli.makinen, alexandru.tomescu, anna.kuosmanen}@helsinki.fi; T. Gagie, EIT, Diego Portales University, Av. Ejército 441, Santiago, Chile; email: travis.gagie@gmail.com; R. Chikhi, CNRS, CRIStAL, University of Lille, Bâtiment M3 extension, Avenue Carl Gauss, Villeneuve d’Ascq Cedex, 59655, France; email: rayan.chikhi@univ-lille.fr. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. 1549-6325/2019/02-ART29 $15.00 https://doi.org/10.1145/3301312