Zobrazeno 1 - 10
of 721
pro vyhledávání: '"P. Mulzer"'
Robust Algorithms for Finding Triangles and Computing the Girth in Unit Disk and Transmission Graphs
Autor:
Klost, Katharina, Mulzer, Wolfgang
We describe optimal robust algorithms for finding a triangle and the unweighted girth in a unit disk graph, as well as finding a triangle in a transmission graph.In the robust setting, the input is not given as a set of sites in the plane, but rather
Externí odkaz:
http://arxiv.org/abs/2405.01180
Let $S \subseteq \mathbb{R}^2$ be a set of $n$ \emph{sites} in the plane, so that every site $s \in S$ has an \emph{associated radius} $r_s > 0$. Let $D(S)$ be the \emph{disk intersection graph} defined by $S$, i.e., the graph with vertex set $S$ and
Externí odkaz:
http://arxiv.org/abs/2306.15338
A family of $k$ point sets in $d$ dimensions is well-separated if the convex hulls of any two disjoint subfamilies can be separated by a hyperplane. Well-separation is a strong assumption that allows us to conclude that certain kinds of generalized h
Externí odkaz:
http://arxiv.org/abs/2209.02319
Autor:
Cleve, Jonas, Grelier, Nicolas, Knorr, Kristin, Löffler, Maarten, Mulzer, Wolfgang, Perz, Daniel
Let $\mathcal{D}$ be a set of straight-line segments in the plane, potentially crossing, and let $c$ be a positive integer. We denote by $P$ the union of the endpoints of the straight-line segments of $\mathcal{D}$ and of the intersection points betw
Externí odkaz:
http://arxiv.org/abs/2209.02103
The complexity classes Unique End of Potential Line (UEOPL) and its promise version PUEOPL were introduced in 2018 by Fearnly et al. UEOPL captures search problems where the instances are promised to have a unique solution. UEOPL captures total searc
Externí odkaz:
http://arxiv.org/abs/2209.02101
Autor:
Aichholzer, Oswin, Knorr, Kristin, Mulzer, Wolfgang, Maalouly, Nicolas El, Obenaus, Johannes, Paul, Rosna, Reddy, Meghana M., Vogtenhuber, Birgit, Weinberger, Alexandra
For a simple drawing $D$ of the complete graph $K_n$, two (plane) subdrawings are compatible if their union is plane. Let $\mathcal{T}_D$ be the set of all plane spanning trees on $D$ and $\mathcal{F}(\mathcal{T}_D)$ be the compatibility graph that h
Externí odkaz:
http://arxiv.org/abs/2208.11875
Autor:
Aichholzer, Oswin, Knorr, Kristin, Mulzer, Wolfgang, Obenaus, Johannes, Paul, Rosna, Vogtenhuber, Birgit
Let $S$ be a planar point set in general position, and let $\mathcal{P}(S)$ be the set of all plane straight-line paths with vertex set $S$. A flip on a path $P \in \mathcal{P}(S)$ is the operation of replacing an edge $e$ of $P$ with another edge $f
Externí odkaz:
http://arxiv.org/abs/2202.10831
Autor:
Staat, Paul, Mulzer, Simon, Roth, Stefan, Moonsamy, Veelasha, Heinrichs, Markus, Kronberger, Rainer, Sezgin, Aydin, Paar, Christof
Wireless radio channels are known to contain information about the surrounding propagation environment, which can be extracted using established wireless sensing methods. Thus, today's ubiquitous wireless devices are attractive targets for passive ea
Externí odkaz:
http://arxiv.org/abs/2112.01967
Autor:
Baumann, Alexander, Kaplan, Haim, Klost, Katharina, Knorr, Kristin, Mulzer, Wolfgang, Roditty, Liam, Seiferth, Paul
Publikováno v:
Discrete and Computational Geometry (DCG), 71(1), Jan 2024, pp. 214.277
Let $S$ be a set of $n$ sites in the plane, so that every site $s \in S$ has an associated radius $r_s > 0$. Let $\mathcal{D}(S)$ be the disk intersection graph defined by $S$, i.e., the graph with vertex set $S$ and an edge between two distinct site
Externí odkaz:
http://arxiv.org/abs/2106.14935
In the longest plane spanning tree problem, we are given a finite planar point set $\mathcal{P}$, and our task is to find a plane (i.e., noncrossing) spanning tree for $\mathcal{P}$ with maximum total Euclidean edge length. Despite more than two deca
Externí odkaz:
http://arxiv.org/abs/2101.00445