 Home
 Search Results
 Page 1 of 1
Search for: All records

Total Resources3
 Resource Type

30
 Availability

30
 Author / Contributor
 Filter by Author / Creator


Levi, Reut (3)

Rubinfeld, Ronitt (3)

Ron, Dana (2)

Moshkovitz, Guy (1)

Shapira, Asaf (1)

Yodpinyanee, Anak (1)

#Tyler Phillips, Kenneth E. (0)

& *Soto, E. (0)

& Ahmed, Khadija. (0)

& AkcilOkan, O. (0)

& Akuom, D. (0)

& AndrewsLarson, C. (0)

& Archibald, J. (0)

& Attari, S. Z. (0)

& Ayala, O. (0)

& Babbitt, W. (0)

& Baek, Y. (0)

& Bai, F. (0)

& BarthCohen, L. (0)

& Bassett, L. (0)

 Filter by Editor


& Ahn, J. (0)

& Bateiha, S. (0)

& Chen, B. (0)

& Chen, Bodong (0)

& Kali, Y. (0)

& RuizArias, P.M. (0)

& Spitzer, S. (0)

& Spitzer, S.M. (0)

:Chaosong Huang, Gang Lu (0)

A. Beygelzimer (0)

A. Ghate, K. Krishnaiyer (0)

A. I. Sacristán, J. C. (0)

A. Weinberg, D. MooreRusso (0)

A. Weinberger (0)

A.I. Sacristán, J.C. CortésZavala (0)

A.I., Dimitrova (0)

ACS (0)

AIAA (0)

AIAA Propulsion and Energy 2021 (0)

AIAA SciTech (0)


Have feedback or suggestions for a way to improve these results?
!
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxation is that the constructed subgraph is a sparse spanning subgraph containing at most (1+ϵ)n edges (where n is the number of vertices and ϵ is a given approximation/sparsity parameter). In the local setting, the goal is to quickly determine whether a given edge e belongs to such a subgraph, without constructing the whole subgraph, but rather by inspecting (querying) the local neighborhood of e. The challenge ismore »

Levi, Reut ; Rubinfeld, Ronitt ; Yodpinyanee, Anak ( , Algorithmica)In the model of local computation algorithms (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. Many recently developed LCAs on graph problems achieve time and space complexities with very low dependence on n, the number of vertices. Nonetheless, these complexities are generally at least exponential in d, the upper bound on the degree of the input graph. Instead, we consider the case where parameter d can be moderately dependent on n, and aim for complexities with subexponential dependence on d, while maintaining polylogarithmic dependence on n. Wemore »present: a randomized LCA for computing maximal independent sets whose time and space complexities are quasipolynomial in d and polylogarithmic in n; for constant ε>0, a randomized LCA that provides a (1−ε)approximation to maximum matching with high probability, whose time and space complexities are polynomial in d and polylogarithmic in n.« less

Levi, Reut ; Moshkovitz, Guy ; Ron, Dana ; Rubinfeld, Ronitt ; Shapira, Asaf ( , Random structures & algorithms)Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected boundeddegree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph math formula consisting of math formula edges (for a prespecified constant math formula), where the decision for different edges should be consistent with the same subgraph math formula. Can this task be performed by inspecting only a constant number of edgesmore »in G? Our main results are: We show that if every tvertex subgraph of G has expansion math formula then one can (deterministically) construct a sparse spanning subgraph math formula of G using few inspections. To this end we analyze a “local” version of a famous minimumweight spanning tree algorithm. We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3regular graphs of high girth, in which every tvertex subgraph has expansion math formula. We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth.« less