Zobrazeno 1 - 7
of 7
pro vyhledávání: '"Jakub Lacki"'
We study stochastic dynamics of the Prisoner's Dilemma game on random Erd\"{o}s-R\'{e}nyi and scale-free Barab\'{a}si-Albert networks with a cost of maintaining a link between interacting players. We show that when the cost increases, the population
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b12c723ab42cb9ada5242def2691ab6b
Graph clustering and community detection are central problems in modern data mining. The increasing need for analyzing billion-scale data calls for faster and more scalable algorithms for these problems. There are certain trade-offs between the quali
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a897d5af99e6691f28675bcb41d1656a
Autor:
Jakub Lacki, Soheil Behnezhad, Laxman Dhulipala, Warren Schudy, Vahab Mirrokni, Hossein Esfandiari
Publikováno v:
VLDB Endowment
We study fundamental graph problems such as graph connectivity, minimum spanning forest (MSF), and approximate maximum (weight) matching in a distributed setting. In particular, we focus on the Adaptive Massively Parallel Computation (AMPC) model, wh
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::626f7dc02dd49f680c106ae2ea4bc017
http://arxiv.org/abs/2009.11552
http://arxiv.org/abs/2009.11552
Publikováno v:
FOCS
Identifying the connected components of a graph, apart from being a fundamental problem with countless applications, is a key primitive for many other algorithms. In this paper, we consider this problem in parallel settings. Particularly, we focus on
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::021dcab3cff856296bea6996c188ae29
Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time
Publikováno v:
Chechik, S, Hansen, T D, Italiano, G F, Łącki, J & Parotsidis, N 2016, Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time . in 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) . IEEE, pp. 315-324, New Brunswick, New Jersey, United States, 09/10/2016 . https://doi.org/10.1109/FOCS.2016.42
FOCS
FOCS
We present randomized algorithms with a total update time of O(m √n) for the problems of decremental single source reachability and decremental strongly connected components on directed graphs. This improves recent breakthrough results of Henzinger
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f920fd4ccac82b925228c4bbf8ae914c
https://pure.au.dk/portal/da/publications/decremental-singlesource-reachability-and-strongly-connected-components-in-omn-total-update-time(6144ce7c-5b03-4c71-b75c-50e283517d8d).html
https://pure.au.dk/portal/da/publications/decremental-singlesource-reachability-and-strongly-connected-components-in-omn-total-update-time(6144ce7c-5b03-4c71-b75c-50e283517d8d).html
Autor:
Piotr Sankowski, Jakub Lacki
Publikováno v:
ITCS
In this paper we consider the problem of maintaining information about graphs with history -- so called graph timeline. A graph timeline is a sequence of graphs G1,..., Gt, in which consecutive graphs are obtained from previous ones by small modifica
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::51c2b8eff3ed5d3d3386eaffe9c6e140
https://doi.org/10.1145/2422436.2422468
https://doi.org/10.1145/2422436.2422468
Publikováno v:
FOCS
Let G = (V,E) be a planar n-vertex digraph. Consider the problem of computing max st-flow values in G from a fixed source s to all sinks t in V\{s}. We show how to solve this problem in near-linear O(n log^3 n) time. Previously, no better solution wa
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::30568dfa9f2b02dc0af5c2c6102f639b