Zobrazeno 1 - 10
of 369
pro vyhledávání: '"Welzl, Emo"'
Autor:
Lengler, Johannes, Martinsson, Anders, Petrova, Kalina, Schnider, Patrick, Steiner, Raphael, Weber, Simon, Welzl, Emo
For any positive edge density $p$, a random graph in the Erd\H{o}s-Renyi $G_{n,p}$ model is connected with non-zero probability, since all edges are mutually independent. We consider random graph models in which edges that do not share endpoints are
Externí odkaz:
http://arxiv.org/abs/2305.02974
Autor:
GOAOC, XAVIER1 xavier.goaoc@loria.fr, WELZL, EMO2 emo@inf.ethz.ch
Publikováno v:
Journal of the ACM. Feb2023, Vol. 70 Issue 1, p1-47. 47p.
We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is $\alpha$-stable if the underlying optimal clustering continues to remain optimal even when all pairwise
Externí odkaz:
http://arxiv.org/abs/2009.14358
Autor:
Wagner, Uli, Welzl, Emo
Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation is a full triangulation of some subset P' of P containing all extreme points in P. A biste
Externí odkaz:
http://arxiv.org/abs/2003.13557
Autor:
Goaoc, Xavier, Welzl, Emo
We establish the following two main results on order types of points in general position in the plane (realizable simple planar order types, realizable uniform acyclic oriented matroids of rank $3$): (a) The number of extreme points in an $n$-point o
Externí odkaz:
http://arxiv.org/abs/2003.08456
Autor:
Bertschinger, Daniel, Lengler, Johannes, Martinsson, Anders, Meier, Robert, Steger, Angelika, Trujić, Miloš, Welzl, Emo
Consider the following simple coloring algorithm for a graph on $n$ vertices. Each vertex chooses a color from $\{1, \dotsc, \Delta(G) + 1\}$ uniformly at random. While there exists a conflicted vertex choose one such vertex uniformly at random and r
Externí odkaz:
http://arxiv.org/abs/2002.05121
Autor:
Aichholzer, Oswin, Balko, Martin, Hoffmann, Michael, Kynčl, Jan, Mulzer, Wolfgang, Parada, Irene, Pilz, Alexander, Scheucher, Manfred, Valtr, Pavel, Vogtenhuber, Birgit, Welzl, Emo
Publikováno v:
Journal of Graph Algorithms and Applications 24 (2020), no. 4, 551-572
In order to have a compact visualization of the order type of a given point set S, we are interested in geometric graphs on S with few edges that unambiguously display the order type of S. We introduce the concept of exit edges, which prevent the ord
Externí odkaz:
http://arxiv.org/abs/1908.05124
A set $P = H \cup \{w\}$ of $n+1$ points in general position in the plane is called a wheel set if all points but $w$ are extreme. We show that for the purpose of counting crossing-free geometric graphs on such a set $P$, it suffices to know the freq
Externí odkaz:
http://arxiv.org/abs/1812.01595
We investigate parameterizing hard combinatorial problems by the size of the solution set compared to all solution candidates. Our main result is a uniform sampling algorithm for satisfying assignments of 2-CNF formulas that runs in expected time $O^
Externí odkaz:
http://arxiv.org/abs/1708.01122
Autor:
Aichholzer, Oswin, Hackl, Thomas, Korman, Matias, van Kreveld, Marc, Löffler, Maarten, Pilz, Alexander, Speckmann, Bettina, Welzl, Emo
We consider the following question: How many edge-disjoint plane spanning trees are contained in a complete geometric graph $GK_n$ on any set $S$ of $n$ points in general position in the plane? We show that this number is in $\Omega(\sqrt{n})$. Furth
Externí odkaz:
http://arxiv.org/abs/1707.05440