Главная

Alexander Wolff

  1. Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability.

    Пт, 09/17/2010 - 15:02 — SomNambul
    Authors: Yoshio Okamoto, Kevin Buchin, Alexander Wolff, Rodrigo I. Silveira, Martin Nöllenburg, Maike Buchin, Jaroslaw Byrka
    Subjects: Computational Geometry
    Abstract

    A \emph{binary tanglegram} is a drawing of a pair of rooted binary trees
    whose leaf sets are in one-to-one correspondence; matching leaves are connected
    by inter-tree edges. For applications, for example, in phylogenetics, it is
    essential that both trees are drawn without edge crossings and that the
    inter-tree edges have as few crossings as possible. It is known that finding a
    tanglegram with the minimum number of crossings is NP-hard and that the problem
    is fixed-parameter tractable with respect to that number.

  2. The Traveling Salesman Problem Under Squared Euclidean Distances.

    Втр, 01/05/2010 - 16:01 — SomNambul
    Authors: Mark de Berg, Fred van Nijnatten, René Sitters, Gerhard J. Woeginger, Alexander Wolff
    Subjects: Computational Geometry
    Abstract

    Let $P$ be a set of points in $\mathbb{R}^d$, and let $\alpha \ge 1$ be a
    real number. We define the distance between two points $p,q\in P$ as
    $|pq|^{\alpha}$, where $|pq|$ denotes the standard Euclidean distance between
    $p$ and $q$. We denote the traveling salesman problem under this distance
    function by TSP($d,\alpha$). We design a 5-approximation algorithm for TSP(2,2)
    and generalize this result to obtain an approximation factor of
    $3^{\alpha-1}+\sqrt{6}^{\alpha}/3$ for $d=2$ and all $\alpha\ge2$.

Math-arch

RSS-материал