Zobrazeno 1 - 10
of 19
pro vyhledávání: '"Klost, Katharina"'
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
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
Autor:
Kaplan, Haim, Klost, Katharina, Mulzer, Wolfgang, Roditty, Liam, Seiferth, Paul, Sharir, Micha
Let $S \subset \mathbb{R}^2$ be a set of $n$ sites, where each $s \in S$ has an associated radius $r_s > 0$. The disk graph $D(S)$ is the undirected graph with vertex set $S$ and an undirected edge between two sites $s, t \in S$ if and only if $|st|
Externí odkaz:
http://arxiv.org/abs/1907.01980
Autor:
Chiu, Man-Kwun, Cleve, Jonas, Klost, Katharina, Korman, Matias, Mulzer, Wolfgang, van Renssen, André, Roeloffzen, Marcel, Willert, Max
Let $P$ be an $x$-monotone orthogonal polygon with $n$ vertices. We call $P$ a simple histogram if its upper boundary is a single edge; and a double histogram if it has a horizontal chord from the left boundary to the right boundary. Two points $p$ a
Externí odkaz:
http://arxiv.org/abs/1902.06599
Autor:
Klost, Katharina
Publikováno v:
In Computational Geometry: Theory and Applications April 2023 111
Autor:
Klost, Katharina, Mulzer, Wolfgang
Suppose we have an arrangement $\mathcal{A}$ of $n$ geometric objects $x_1, \dots, x_n \subseteq \mathbb{R}^2$ in the plane, with a distinguished point $p_i$ in each object $x_i$. The generalized transmission graph of $\mathcal{A}$ has vertex set $\{
Externí odkaz:
http://arxiv.org/abs/1712.07559
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
Leibniz International Proceedings in Informatics (LIPIcs), 224
38th International Symposium on Computational Geometry
38th International Symposium on Computational Geometry
In the longest plane spanning tree problem, we are given a finite planar point set P, and our task is to find a plane (i.e., noncrossing) spanning tree TOPT for P with maximum total Euclidean edge length |TOPT|. Despite more than two decades of resea
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1928e2f82166977038fede1d6c6544f1