Zobrazeno 1 - 10
of 34
pro vyhledávání: '"Amir Abboud"'
Autor:
Amir Abboud
Publikováno v:
آداب الكوفة, Vol 1, Iss 47 (2021)
يكتسب موضوع البحث (أدوات ودوافع حروب الجيل الخامس) أهمية كبيرة, وذلك بسبب حداثة هذا المصطلح, فضلاً عن التطور الذي حدث على مستوى الوسائل ال
Externí odkaz:
https://doaj.org/article/e56330cd5d724dfbaf0115b0939edd1e
Publikováno v:
Symposium on Simplicity in Algorithms (SOSA) ISBN: 9781611977585
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1e22380019e993ba754a70067183dd84
https://doi.org/10.1137/1.9781611977585.ch14
https://doi.org/10.1137/1.9781611977585.ch14
Publikováno v:
ACM Transactions on Algorithms. 17:1-40
This paper proves strong lower bounds for distributed computing in the CONGEST model, by presenting the bit-gadget: a new technique for constructing graphs with small cuts. The contribution of bit-gadgets is twofold. First, developing careful sparse
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b3bd175ee564d3db171c08cf701b4735
https://doi.org/10.1145/3469834
https://doi.org/10.1145/3469834
Publikováno v:
STOC '22
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing
We present a new technique for efficiently removing almost all short cycles in a graph without unintentionally removing its triangles. Consequently, triangle finding problems do not become easy even in almost $k$-cycle free graphs, for any constant $
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::57519f3de34f824b96de5f3e09dc97ea
http://arxiv.org/abs/2204.10465
http://arxiv.org/abs/2204.10465
Publikováno v:
STOC
Every undirected graph G has a (weighted) cut-equivalent tree T, commonly named after Gomory and Hu who discovered it in 1961. Both T and G have the same node set, and for every node pair s,t, the minimum (s,t)-cut in T is also an exact minimum (s,t)
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8ca8ff04f1a849d6dcf3fa1360cc17b5
https://doi.org/10.1145/3406325.3451073
https://doi.org/10.1145/3406325.3451073
We design an $n^{2+o(1)}$-time algorithm that constructs a cut-equivalent (Gomory-Hu) tree of a simple graph on $n$ nodes. This bound is almost-optimal in terms of $n$, and it improves on the recent $\tilde{O}(n^{2.5})$ bound by the authors (STOC 202
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::062e5756cd363056cc7dcc18916966d1
Autor:
Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi
In 1961, Gomory and Hu showed that the All-Pairs Max-Flow problem of computing the max-flow between all $n\choose 2$ pairs of vertices in an undirected graph can be solved using only $n-1$ calls to any (single-pair) max-flow algorithm. Even assuming
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b232e05d7d58ced5408dfb9c80bdbc34
Publikováno v:
FOCS
Min-Cut queries are fundamental: Preprocess an undirected edge-weighted graph, to quickly report a minimum-weight cut that separates a query pair of nodes $s, t$ . The best data structure known for this problem simply builds a cut-equivalent tree, di
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::64ee2c33f36e7e4763625be3faf39902
https://doi.org/10.1109/focs46700.2020.00019
https://doi.org/10.1109/focs46700.2020.00019
Publikováno v:
STOC
The Sparsest Cut is a fundamental optimization problem that have been extensively studied. For planar inputs the problem is in P and can be solved in O(n 3 ) time if all vertex weights are 1. Despite a significant amount of effort, the best algorithm
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::eda3c433d3b56cca7632ceaef24cc403
http://arxiv.org/abs/2007.02377
http://arxiv.org/abs/2007.02377