Zobrazeno 1 - 10
of 54
pro vyhledávání: '"Kisfaludi P"'
Autor:
Bläsius, Thomas, von der Heydt, Jean-Pierre, Kisfaludi-Bak, Sándor, Wilhelm, Marcus, van Wordragen, Geert
We consider intersection graphs of disks of radius $r$ in the hyperbolic plane. Unlike the Euclidean setting, these graph classes are different for different values of $r$, where very small $r$ corresponds to an almost-Euclidean setting and $r \in \O
Externí odkaz:
http://arxiv.org/abs/2407.09362
Autor:
Kisfaludi-Bak, Sándor, Masaříková, Jana, van Leeuwen, Erik Jan, Walczak, Bartosz, Węgrzycki, Karol
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incomparable. Motivated by the broad study of algorithms and separators on pl
Externí odkaz:
http://arxiv.org/abs/2310.11283
We propose a data structure in $d$-dimensional hyperbolic space that can be considered a natural counterpart to quadtrees in Euclidean spaces. Based on this data structure we propose a so-called L-order for hyperbolic point sets, which is an extensio
Externí odkaz:
http://arxiv.org/abs/2305.01356
A polygon C is an intersecting polygon for a set O of objects in the plane if C intersects each object in O, where the polygon includes its interior. We study the problem of computing the minimum-perimeter intersecting polygon and the minimum-area co
Externí odkaz:
http://arxiv.org/abs/2208.07567
In the Directed Steiner Network problem, the input is a directed graph G, a subset T of k vertices of G called the terminals, and a demand graph D on T. The task is to find a subgraph H of G with the minimum number of edges such that for every edge (
Externí odkaz:
http://arxiv.org/abs/2208.06015
The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves $\pi, \sigma$ in $\mathbb{R}^d$, it provides a robust, outlier-insensitive alternative to the Fr\'echet distance
Externí odkaz:
http://arxiv.org/abs/2203.07898
We initiate the study of diameter computation in geometric intersection graphs from the fine-grained complexity perspective. A geometric intersection graph is a graph whose vertices correspond to some shapes in $d$-dimensional Euclidean space, such a
Externí odkaz:
http://arxiv.org/abs/2203.03663
A homomorphism from a graph $G$ to a graph $H$ is an edge-preserving mapping from $V(G)$ to $V(H)$. Let $H$ be a fixed graph with possible loops. In the list homomorphism problem, denoted by \textsc{LHom}($H$), the instance is a graph $G$, whose ever
Externí odkaz:
http://arxiv.org/abs/2202.08896
Let $F$ be a set of $n$ objects in the plane and let $G(F)$ be its intersection graph. A balanced clique-based separator of $G(F)$ is a set $S$ consisting of cliques whose removal partitions $G(F)$ into components of size at most $\delta n$, for some
Externí odkaz:
http://arxiv.org/abs/2109.09874
We consider the online search problem in which a server starting at the origin of a $d$-dimensional Euclidean space has to find an arbitrary hyperplane. The best-possible competitive ratio and the length of the shortest curve from which each point on
Externí odkaz:
http://arxiv.org/abs/2109.04340