Zobrazeno 1 - 6
of 6
pro vyhledávání: '"Rutschmann, Daniel"'
Fredman proposed in 1976 the following algorithmic problem: Given are a ground set $X$, some partial order $P$ over $X$, and some comparison oracle $O_L$ that specifies a linear order $L$ over $X$ that extends $P$. A query to $O_L$ has as input disti
Externí odkaz:
http://arxiv.org/abs/2407.21591
Autor:
van der Hoog, Ivor, Rutschmann, Daniel
Sorting has a natural generalization where the input consists of: (1) a ground set $X$ of size $n$, (2) a partial oracle $O_P$ specifying some fixed partial order $P$ on $X$ and (3) a linear oracle $O_L$ specifying a linear order $L$ that extends $P$
Externí odkaz:
http://arxiv.org/abs/2404.08468
We show that every planar triangulation on $n>10$ vertices has a dominating set of size $n/7=n/3.5$. This approaches the $n/4$ bound conjectured by Matheson and Tarjan [MT'96], and improves significantly on the previous best bound of $17n/53\approx n
Externí odkaz:
http://arxiv.org/abs/2310.11254
Autor:
Rutschmann, Daniel, Wettstein, Manuel
We introduce the abstract notion of a chain, which is a sequence of $n$ points in the plane, ordered by $x$-coordinates, so that the edge between any two consecutive points is unavoidable as far as triangulations are concerned. A general theory of th
Externí odkaz:
http://arxiv.org/abs/2203.07584
Autor:
RUTSCHMANN, DANIEL1 daru@dtu.dk, WETTSTEIN, MANUEL1 manuelwe@inf.ethz.ch
Publikováno v:
Journal of the ACM. Jun2023, Vol. 70 Issue 3, p1-26. 26p.
Publikováno v:
Huang, S, Liu, C H & Rutschmann, D 2023, Approximate Selection with Unreliable Comparisons in Optimal Expected Time . in Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science : STACS 2023 ., 37, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, 07/03/2023 . https://doi.org/10.4230/LIPIcs.STACS.2023.37
Given n elements, an integer k ≤ n/2 and a parameter ε ≥ 1/n, we study the problem of selecting an element with rank in (k-nε, k+nε] using unreliable comparisons where the outcome of each comparison is incorrect independently with a constant e
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::90b6707132394904a188a5df6a6985b4