Zobrazeno 1 - 10
of 190
pro vyhledávání: '"PARTER, MERAV"'
The dual of a planar graph $G$ is a planar graph $G^*$ that has a vertex for each face of $G$ and an edge for each pair of adjacent faces of $G$. The profound relationship between a planar graph and its dual has been the algorithmic basis for solving
Externí odkaz:
http://arxiv.org/abs/2411.11718
Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
Autor:
Parter, Merav, Tzalik, Elad
An $f$-edge (or vertex) connectivity certificate is a sparse subgraph that maintains connectivity under the failure of at most $f$ edges (or vertices). It is well known that any $n$-vertex graph admits an $f$-edge (or vertex) connectivity certificate
Externí odkaz:
http://arxiv.org/abs/2411.11054
We provide new algorithms for constructing spanners of arbitrarily edge- or vertex-colored graphs, that can endure up to $f$ failures of entire color classes. The failure of even a single color may cause a linear number of individual edge/vertex faul
Externí odkaz:
http://arxiv.org/abs/2410.07844
We study a new and stronger notion of fault-tolerant graph structures whose size bounds depend on the degree of the failing edge set, rather than the total number of faults. For a subset of faulty edges $F \subseteq G$, the faulty-degree $\deg(F)$ is
Externí odkaz:
http://arxiv.org/abs/2309.06696
We present succinct labeling schemes for answering connectivity queries in graphs subject to a specified number of vertex failures. An $f$-vertex/edge fault tolerant ($f$-V/EFT) connectivity labeling is a scheme that produces succinct labels for the
Externí odkaz:
http://arxiv.org/abs/2307.06276
Autor:
Fischer, Orr, Parter, Merav
In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the study of distributed computation in the presence of mobile adversaries which can dynamically appear throughout the network. Over the years, this setting has been studied mostly under
Externí odkaz:
http://arxiv.org/abs/2305.14300
Autor:
Parter, Merav, Petruschka, Asaf
We present near-optimal algorithms for detecting small vertex cuts in the CONGEST model of distributed computing. Despite extensive research in this area, our understanding of the vertex connectivity of a graph is still incomplete, especially in the
Externí odkaz:
http://arxiv.org/abs/2211.09415
Autor:
Kogan, Shimon, Parter, Merav
Hopsets and spanners are fundamental graph structures, playing a key role in shortest path computation, distributed communication, and more. A (near-exact) hopset for a given graph $G$ is a (small) subset of weighted edges $H$ that when added to the
Externí odkaz:
http://arxiv.org/abs/2211.06920
Autor:
BODWIN, GREG1 bodwin@umich.edu, PARTER, MERAV2 merav.parter@weizmann.ac.il
Publikováno v:
Journal of the ACM. Oct2023, Vol. 70 Issue 5, p1-24. 24p.
