Zobrazeno 1 - 10
of 195
pro vyhledávání: '"Marek Chrobak"'
Publikováno v:
SIAM Journal on Computing. 51:1626-1691
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::eafcfc0ed107ae093a3ecab8a3f0f7f6
https://doi.org/10.1137/21m1469753
https://doi.org/10.1137/21m1469753
Publikováno v:
Acta Informatica, vol 59, iss 6
Huang and Wong (Acta Inform 21(1):113–123, 1984) proposed a polynomial-time dynamic-programming algorithm for computing optimal generalized binary split trees. We show that their algorithm is incorrect. Thus, it remains open whether such trees can
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a317079dfd2753c51afda8d38a2de703
https://doi.org/10.1007/s00236-021-00411-z
https://doi.org/10.1007/s00236-021-00411-z
Autor:
Huong Luu, Marek Chrobak
Publikováno v:
WALCOM: Algorithms and Computation ISBN: 9783031270505
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ac1846cd8eabde3eb129b9d5e6a2e26c
https://doi.org/10.1007/978-3-031-27051-2_15
https://doi.org/10.1007/978-3-031-27051-2_15
Publikováno v:
Theoretical Computer Science. 845:98-121
Some microfluidic lab-on-chip devices contain modules whose function is to mix two fluids, called reactant and buffer, in desired proportions. In one of the technologies for fluid mixing the process can be represented by a directed acyclic graph whos
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4436ecabe958d2638dcd13906a9c3209
https://doi.org/10.1016/j.tcs.2020.09.007
https://doi.org/10.1016/j.tcs.2020.09.007
Publikováno v:
ACM Journal of Experimental Algorithmics. 25:1-22
We address the problem of designing micro-fluidic chips for sample preparation, which is a crucial step in many experimental processes in chemical and biological sciences. One of the objectives of sample preparation is to dilute the sample fluid, cal
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1bbd20af06b44d86dd76a8088dc7cadd
https://doi.org/10.1145/3408297
https://doi.org/10.1145/3408297
Autor:
Marek Chrobak, Łukasz Jeż, Nguyen Kim Thang, Martin Böhm, Pavel Veselý, Jiří Sgall, Christoph Dürr, Jaroslaw Byrka, Marcin Bienkowski, Lukáš Folwarczný
Publikováno v:
Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2021, 861, pp.133-143. ⟨10.1016/j.tcs.2021.02.016⟩
Theoretical Computer Science, 2021, 861, pp.133-143. ⟨10.1016/j.tcs.2021.02.016⟩
Theoretical Computer Science, Elsevier, 2021, 861, pp.133--143. ⟨10.1016/j.tcs.2021.02.016⟩
Theoretical Computer Science, Elsevier, 2021, 861, pp.133-143. ⟨10.1016/j.tcs.2021.02.016⟩
Theoretical Computer Science, 2021, 861, pp.133-143. ⟨10.1016/j.tcs.2021.02.016⟩
Theoretical Computer Science, Elsevier, 2021, 861, pp.133--143. ⟨10.1016/j.tcs.2021.02.016⟩
In the Multi-Level Aggregation Problem ( MLAP ), requests for service arrive at the nodes of an edge-weighted rooted tree T . Each service is represented by a subtree X of T that contains its root. This subtree X serves all requests that are pending
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0186c04d6bcce26ca5e147e16ac11595
https://hal.archives-ouvertes.fr/hal-03377715
https://hal.archives-ouvertes.fr/hal-03377715
We present a simple $O(n^4)$-time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the same running time, but is significantly more complicated and is restricte
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e87a5a70f16f13c1286c0ed1debe7225
http://arxiv.org/abs/2103.01084
http://arxiv.org/abs/2103.01084
Publikováno v:
Information and Computation
We study the problem of information gathering in ad-hoc radio networks without collision detection, focussing on the case when the network forms a tree, with edges directed towards the root. Initially, each node has a piece of information that we ref
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1010219936a4b46d2ed7b9438cfa3061
https://doi.org/10.1016/j.ic.2017.11.003
https://doi.org/10.1016/j.ic.2017.11.003
Publikováno v:
Information and Computation. 281:104707
Search trees are commonly used to implement access operations to a set of stored keys. If this set is static and the probabilities of membership queries are known in advance, then one can precompute an optimal search tree, namely one that minimizes t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::10aa3d1aecc1e85e4e38b0aab6b26306
https://doi.org/10.1016/j.ic.2021.104707
https://doi.org/10.1016/j.ic.2021.104707