Zobrazeno 1 - 10
of 193
pro vyhledávání: '"Chalopin, Jérémie"'
The problem of electing a unique leader is central to all distributed systems, including programmable matter systems where particles have constant size memory. In this paper, we present a silent self-stabilising, deterministic, stationary, election a
Externí odkaz:
http://arxiv.org/abs/2408.08775
We prove that any convex geometry $\mathcal{A}=(U,\mathcal{C})$ on $n$ points and any ideal $\mathcal{I}=(U',\mathcal{C}')$ of $\mathcal{A}$ can be realized as the intersection pattern of an open convex polyhedral cone $K\subseteq {\mathbb R}^n$ with
Externí odkaz:
http://arxiv.org/abs/2405.12660
Leader Election is an important primitive for programmable matter, since it is often an intermediate step for the solution of more complex problems. Although the leader election problem itself is well studied even in the specific context of programma
Externí odkaz:
http://arxiv.org/abs/2402.10582
Autor:
Chalopin, Jérémie, Chepoi, Victor
In this note, we prove that finite CAT(0) cube complexes can be reconstructed from their boundary distances (computed in their 1-skeleta). This result was conjectured by Haslegrave, Scott, Tamitegama, and Tan (2023). The reconstruction of a finite ce
Externí odkaz:
http://arxiv.org/abs/2310.04223
Recently, Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and showed it is the most efficient machine teaching model satisfying the Goldman-Mathias collusion-avoidance criterion. A teaching map $T$ for a c
Externí odkaz:
http://arxiv.org/abs/2309.02876
A set $S$ of isometric paths of a graph $G$ is "$v$-rooted", where $v$ is a vertex of $G$, if $v$ is one of the end-vertices of all the isometric paths in $S$. The isometric path complexity of a graph $G$, denoted by $ipco(G)$, is the minimum integer
Externí odkaz:
http://arxiv.org/abs/2301.00278
Publikováno v:
SIAM Journal on Discrete Mathematics, 37(4):2585-2616, 2023
One of the open problems in machine learning is whether any set-family of VC-dimension $d$ admits a sample compression scheme of size $O(d)$. In this paper, we study this problem for balls in graphs. For a ball $B=B_r(x)$ of a graph $G=(V,E)$, a real
Externí odkaz:
http://arxiv.org/abs/2206.13254
The median function is a location/consensus function that maps any profile $\pi$ (a finite multiset of vertices) to the set of vertices that minimize the distance sum to vertices from $\pi$. The median function satisfies several simple axioms: Anonym
Externí odkaz:
http://arxiv.org/abs/2206.03587
The main goal of this note is to provide a First-Order Logic with Betweenness (FOLB) axiomatization of the main classes of graphs occurring in Metric Graph Theory, in analogy to Tarski's axiomatization of Euclidean geometry. We provide such an axioma
Externí odkaz:
http://arxiv.org/abs/2203.01070