Zobrazeno 1 - 10
of 526
pro vyhledávání: '"E, Tarjan"'
Autor:
Corwin Sinnamon, Robert E. Tarjan
Publikováno v:
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN: 9781611977554
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::29476be219fe2a18e69efb9c67cac6d4
https://doi.org/10.1137/1.9781611977554.ch24
https://doi.org/10.1137/1.9781611977554.ch24
Autor:
Corwin Sinnamon, Robert E. Tarjan
Publikováno v:
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN: 9781611977554
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2d05b5c297ac1d0ae0cd35ef56a977cc
https://doi.org/10.1137/1.9781611977554.ch23
https://doi.org/10.1137/1.9781611977554.ch23
Autor:
Robert E. Tarjan, Uri Zwick
Publikováno v:
Symposium on Simplicity in Algorithms (SOSA) ISBN: 9781611977585
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::838bc63ce0c283813646e35b09de7786
https://doi.org/10.1137/1.9781611977585.ch27
https://doi.org/10.1137/1.9781611977585.ch27
Publikováno v:
ACM Transactions on Algorithms. 17:1-12
We introduce the zip tree, a form of randomized binary search tree that integrates previous ideas into one practical, performant, and pleasant-to-implement package. A zip tree is a binary search tree in which each node has a numeric rank and the tree
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b11bba2c15e790545a4afd46bebf5924
https://doi.org/10.1145/3476830
https://doi.org/10.1145/3476830
Autor:
Robert E. Tarjan, Siddhartha Jayanti
Publikováno v:
Distributed Computing. 34:413-436
We develop and analyze concurrent algorithms for the disjoint set union (“union-find” ) problem in the shared memory, asynchronous multiprocessor model of computation, with CAS (compare and swap) or DCAS (double compare and swap) as the synchroni
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e32b3e4e0b01a989b56ee081abcff434
https://doi.org/10.1007/s00446-020-00388-x
https://doi.org/10.1007/s00446-020-00388-x
Publikováno v:
SPAA
We present an $O(\log d + \log\log_{m/n} n)$-time randomized PRAM algorithm for computing the connected components of an $n$-vertex, $m$-edge undirected graph with maximum component diameter $d$. The algorithm runs on an ARBITRARY CRCW (concurrent-re
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1f20aa906842951e6475601637707509
Publikováno v:
Theory of Computing Systems. 61:987-1010
We consider combinatorial algorithms for the minimum-cost flow problem on networks with unit capacities, and special cases of the problem. Historically, researchers have developed special-purpose algorithms that exploit unit capacities. In contrast,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1f03fe6d80c537f644117f3493be8bc3
https://doi.org/10.1007/s00224-017-9776-7
https://doi.org/10.1007/s00224-017-9776-7
Publikováno v:
PODC
We consider the disjoint set union problem in the asynchronous shared memory multiprocessor computation model. We design a randomized algorithm that performs at most O(log n) work per operation (with high probability), and performs at most O(m #8226;
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7d5ae7299fc98ceb1f523b817695e237
https://doi.org/10.1145/3293611.3331593
https://doi.org/10.1145/3293611.3331593