Phase transitions in the Prisoner's Dilemma game on scale-free networks

Autor: Jacek Miȩkisz, Javad Mohamadichamgavi, Jakub La̧cki

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

Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice

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

Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time

Autor: Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Nikos Parotsidis, Jakub Lacki

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

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

Single Source - All Sinks Max Flows in Planar Digraphs

Autor: Yahav Nussbaum, Jakub Lacki, Piotr Sankowski, Christian Wulff-Nilsen

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

Almost Optimal Exact Distance Oracles for Planar Graphs.

Autor: CHARALAMPOPOULOS, PANAGIOTIS¹ p.charalampopoulos@bbk.ac.uk, GAWRYCHOWSKI, PAWEŁ² gawry@cs.uni.wroc.pl, YAOWEI LONG³ yaoweil@umich.edu, MOZES, SHAY⁴ smozes@runi.ac.il, PETTIE, SETH⁵ pettie@umich.edu, WEIMANN, OREN⁶ oren@cs.haifa.ac.il, WULFF-NILSEN, CHRISTIAN⁷ koolooz@di.ku.dk

Publikováno v: Journal of the ACM. Apr2023, Vol. 70 Issue 2, p1-50. 50p.