Výsledky vyhledávání - "Theory of computation �� Sparsification and spanners"

Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function

Autor: Le, Hung, Milenković, Lazar, Solomon, Shay

In STOC'95 [S. Arya et al., 1995] Arya et al. showed that any set of n points in ℝ^d admits a (1+ε)-spanner with hop-diameter at most 2 (respectively, 3) and O(n log n) edges (resp., O(n log log n) edges). They also gave a general upper bound trad

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::89f141356163a652b02e4b7abf485ab6

Zobrazit plný text záznamu

Nearly Tight Spectral Sparsification of Directed Hypergraphs

Autor: Oko, Kazusato, Sakaue, Shinsaku, Tanigawa, Shin-ichi

Spectral hypergraph sparsification, an attempt to extend well-known spectral graph sparsification to hypergraphs, has been extensively studied over the past few years. For undirected hypergraphs, Kapralov, Krauthgamer, Tardos, and Yoshida (2022) have

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::4dbef718c9e42e8fc41fd67475def726

Zobrazit plný text záznamu

Efficient Yao Graph Construction

Autor: Funke, Daniel, Sanders, Peter

Yao graphs are geometric spanners that connect each point of a given point set to its nearest neighbor in each of k cones drawn around it. Yao graphs were introduced to construct minimum spanning trees in d dimensional spaces. Moreover, they are used

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::285c0a1e6ea19faf3ff2399c0d4abe7f

Zobrazit plný text záznamu

An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk)

Autor: Kyng, Rasmus

In this talk, I will explain a new algorithm for computing exact maximum and minimum-cost flows in almost-linear time, settling the time complexity of these basic graph problems up to subpolynomial factors. Our algorithm uses a novel interior point m

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::8b1b1e9b45857b73ebb0fdac197ba854

Zobrazit plný text záznamu

Coresets for Clustering in Geometric Intersection Graphs

Autor: Bandyapadhyay, Sayan, Fomin, Fedor V., Inamdar, Tanmay

Designing coresets - small-space sketches of the data preserving cost of the solutions within (1± ε)-approximate factor - is an important research direction in the study of center-based k-clustering problems, such as k-means or k-median. Feldman an

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::205402349ee488e1379c5876c07dca38

Zobrazit plný text záznamu

Improved weighted additive spanners

Autor: Elkin, Michael, Gitlitz, Yuval, Neiman, Ofer

Publikováno v: Distributed Computing.

Graph spanners and emulators are sparse structures that approximately preserve distances of the original graph. While there has been an extensive amount of work on additive spanners, so far little attention was given to weighted graphs. Only very rec

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::00094e411197265f34b3352949860fcd
https://doi.org/10.1007/s00446-022-00433-x

Zobrazit plný text záznamu

Vertex Sparsifiers for Hyperedge Connectivity

Autor: Jiang, Han, Huang, Shang-En, Saranurak, Thatchaphol, Zhang, Tian

Recently, Chalermsook et al. [SODA'21(arXiv:2007.07862)] introduces a notion of vertex sparsifiers for $c$-edge connectivity, which has found applications in parameterized algorithms for network design and also led to exciting dynamic algorithms for

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::15f2abe00d42911037a0f6eb94d8a1da
http://arxiv.org/abs/2207.04115

Zobrazit plný text záznamu

Distributed Construction of Lightweight Spanners for Unit Ball Graphs

Autor: Eppstein, David, Khodabandeh, Hadi

Resolving an open question from 2006 [Damian et al., 2006], we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple 𝒪(log^*n)-round distributed algori

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::006ee3eaae9232395e7ea19c9a2ac4e3

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání