16 Search Results for "Rote, Günter"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.69
A Subexponential Algorithm for ARRIVAL

Authors: Bernd Gärtner, Sebastian Haslebacher, and Hung P. Hoang

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The ARRIVAL problem is to decide the fate of a train moving along the edges of a directed graph, according to a simple (deterministic) pseudorandom walk. The problem is in NP∩coNP but not known to be in 𝖯. The currently best algorithms have runtime 2^Θ(n) where n is the number of vertices. This is not much better than just performing the pseudorandom walk. We develop a subexponential algorithm with runtime 2^O(√nlog n). We also give a polynomial-time algorithm if the graph is almost acyclic. Both results are derived from a new general approach to solve ARRIVAL instances.
Cite as

Bernd Gärtner, Sebastian Haslebacher, and Hung P. Hoang. A Subexponential Algorithm for ARRIVAL. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gartner_et_al:LIPIcs.ICALP.2021.69,
  author =	{G\"{a}rtner, Bernd and Haslebacher, Sebastian and Hoang, Hung P.},
  title =	{{A Subexponential Algorithm for ARRIVAL}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{69:1--69:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.69},
  URN =		{urn:nbn:de:0030-drops-141387},
  doi =		{10.4230/LIPIcs.ICALP.2021.69},
  annote =	{Keywords: Pseudorandom walks, reachability, graph games, switching systems}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.26
Diverse Pairs of Matchings

Authors: Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, and Danil Sagunov

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP-complete on general graphs if k is part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show that Diverse Pair of Maximum Matchings is FPT parameterized by k. We round off the work by showing that Diverse Pair of Matchings has a kernel on 𝒪(k²) vertices.
Cite as

Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, and Danil Sagunov. Diverse Pairs of Matchings. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 26:1-26:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ISAAC.2020.26,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Jaffke, Lars and Philip, Geevarghese and Sagunov, Danil},
  title =	{{Diverse Pairs of Matchings}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{26:1--26:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.26},
  URN =		{urn:nbn:de:0030-drops-133706},
  doi =		{10.4230/LIPIcs.ISAAC.2020.26},
  annote =	{Keywords: Matching, Solution Diversity, Fixed-Parameter Tractability}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.1
An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons

Authors: Eyal Ackerman, Balázs Keszegh, and Günter Rote

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even. If both m and n are odd, the best known construction has mn-(m+n)+3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only mn-(m + ⌈ n/6 ⌉), for m ≥ n. We prove a new upper bound of mn-(m+n)+C for some constant C, which is optimal apart from the value of C.
Cite as

Eyal Ackerman, Balázs Keszegh, and Günter Rote. An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ackerman_et_al:LIPIcs.SoCG.2020.1,
  author =	{Ackerman, Eyal and Keszegh, Bal\'{a}zs and Rote, G\"{u}nter},
  title =	{{An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.1},
  URN =		{urn:nbn:de:0030-drops-121591},
  doi =		{10.4230/LIPIcs.SoCG.2020.1},
  annote =	{Keywords: Simple polygon, Ramsey theory, combinatorial geometry}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.1
Finding and Counting Permutations via CSPs

Authors: Benjamin Aram Berendsohn, László Kozma, and Dániel Marx

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science, going back at least to the seminal work of Knuth on stack-sorting (1968). Perhaps the most natural algorithmic question in this area is deciding whether a given permutation of length n contains a given pattern of length k. In this work we give two new algorithms for this well-studied problem, one whose running time is n^{k/4 + o(k)}, and a polynomial-space algorithm whose running time is the better of O(1.6181^n) and O(n^{k/2 + 1}). These results improve the earlier best bounds of n^{0.47k + o(k)} and O(1.79^n) due to Ahal and Rabinovich (2000) resp. Bruner and Lackner (2012) and are the fastest algorithms for the problem when k in Omega(log{n}). We show that both our new algorithms and the previous exponential-time algorithms in the literature can be viewed through the unifying lens of constraint-satisfaction. Our algorithms can also count, within the same running time, the number of occurrences of a pattern. We show that this result is close to optimal: solving the counting problem in time f(k) * n^{o(k/log{k})} would contradict the exponential-time hypothesis (ETH). For some special classes of patterns we obtain improved running times. We further prove that 3-increasing and 3-decreasing permutations can, in some sense, embed arbitrary permutations of almost linear length, which indicates that an algorithm with sub-exponential running time is unlikely, even for patterns from these restricted classes.
Cite as

Benjamin Aram Berendsohn, László Kozma, and Dániel Marx. Finding and Counting Permutations via CSPs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{berendsohn_et_al:LIPIcs.IPEC.2019.1,
  author =	{Berendsohn, Benjamin Aram and Kozma, L\'{a}szl\'{o} and Marx, D\'{a}niel},
  title =	{{Finding and Counting Permutations via CSPs}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.1},
  URN =		{urn:nbn:de:0030-drops-114627},
  doi =		{10.4230/LIPIcs.IPEC.2019.1},
  annote =	{Keywords: permutations, pattern matching, constraint satisfaction, exponential time}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.9
Geometric Multicut

Authors: Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, and Günter Rote

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as GEOMETRIC k-CUT, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n^4 log^3 n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a (2-4/3k)-approximation algorithm.
Cite as

Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, and Günter Rote. Geometric Multicut. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.ICALP.2019.9,
  author =	{Abrahamsen, Mikkel and Giannopoulos, Panos and L\"{o}ffler, Maarten and Rote, G\"{u}nter},
  title =	{{Geometric Multicut}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.9},
  URN =		{urn:nbn:de:0030-drops-105850},
  doi =		{10.4230/LIPIcs.ICALP.2019.9},
  annote =	{Keywords: multicut, clustering, Steiner tree}
}
Document
DOI: 10.4230/OASIcs.SOSA.2019.1
Isotonic Regression by Dynamic Programming

Authors: Günter Rote

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)

Abstract
For a given sequence of numbers, we want to find a monotonically increasing sequence of the same length that best approximates it in the sense of minimizing the weighted sum of absolute values of the differences. A conceptually easy dynamic programming approach leads to an algorithm with running time O(n log n). While other algorithms with the same running time are known, our algorithm is very simple. The only auxiliary data structure that it requires is a priority queue. The approach extends to other error measures.
Cite as

Günter Rote. Isotonic Regression by Dynamic Programming. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{rote:OASIcs.SOSA.2019.1,
  author =	{Rote, G\"{u}nter},
  title =	{{Isotonic Regression by Dynamic Programming}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{1:1--1:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{69},
  editor =	{Fineman, Jeremy T. and Mitzenmacher, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.1},
  URN =		{urn:nbn:de:0030-drops-100274},
  doi =		{10.4230/OASIcs.SOSA.2019.1},
  annote =	{Keywords: Convex functions, dynamic programming, convex hull, isotonic regression}
}
Document
DOI: 10.4230/OASIcs.SOSA.2019.8
On Primal-Dual Circle Representations

Authors: Stefan Felsner and Günter Rote

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)

Abstract
The Koebe-Andreev-Thurston Circle Packing Theorem states that every triangulated planar graph has a contact representation by circles. The theorem has been generalized in various ways. The most prominent generalization assures the existence of a primal-dual circle representation for every 3-connected planar graph. We present a simple and elegant elementary proof of this result.
Cite as

Stefan Felsner and Günter Rote. On Primal-Dual Circle Representations. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{felsner_et_al:OASIcs.SOSA.2019.8,
  author =	{Felsner, Stefan and Rote, G\"{u}nter},
  title =	{{On Primal-Dual Circle Representations}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{8:1--8:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{69},
  editor =	{Fineman, Jeremy T. and Mitzenmacher, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.8},
  URN =		{urn:nbn:de:0030-drops-100349},
  doi =		{10.4230/OASIcs.SOSA.2019.8},
  annote =	{Keywords: Disk packing, planar graphs, contact representation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.26
Approximate Minimum-Weight Matching with Outliers Under Translation

Authors: Pankaj K. Agarwal, Haim Kaplan, Geva Kipper, Wolfgang Mulzer, Günter Rote, Micha Sharir, and Allen Xiao

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Our goal is to compare two planar point sets by finding subsets of a given size such that a minimum-weight matching between them has the smallest weight. This can be done by a translation of one set that minimizes the weight of the matching. We give efficient algorithms (a) for finding approximately optimal matchings, when the cost of a matching is the L_p-norm of the tuple of the Euclidean distances between the pairs of matched points, for any p in [1,infty], and (b) for constructing small-size approximate minimization (or matching) diagrams: partitions of the translation space into regions, together with an approximate optimal matching for each region.
Cite as

Pankaj K. Agarwal, Haim Kaplan, Geva Kipper, Wolfgang Mulzer, Günter Rote, Micha Sharir, and Allen Xiao. Approximate Minimum-Weight Matching with Outliers Under Translation. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2018.26,
  author =	{Agarwal, Pankaj K. and Kaplan, Haim and Kipper, Geva and Mulzer, Wolfgang and Rote, G\"{u}nter and Sharir, Micha and Xiao, Allen},
  title =	{{Approximate Minimum-Weight Matching with Outliers Under Translation}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{26:1--26:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.26},
  URN =		{urn:nbn:de:0030-drops-99747},
  doi =		{10.4230/LIPIcs.ISAAC.2018.26},
  annote =	{Keywords: Minimum-weight partial matching, Pattern matching, Approximation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.9
Packing Short Plane Spanning Trees in Complete Geometric Graphs

Authors: Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, Günter Rote, André van Renssen, Marcel Roeloffzen, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
Given a set of points in the plane, we want to establish a connection network between these points that consists of several disjoint layers. Motivated by sensor networks, we want that each layer is spanning and plane, and that no edge is very long (when compared to the minimum length needed to obtain a spanning graph). We consider two different approaches: first we show an almost optimal centralized approach to extract two trees. Then we show a constant factor approximation for a distributed model in which each point can compute its adjacencies using only local information. This second approach may create cycles, but maintains planarity.
Cite as

Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, Günter Rote, André van Renssen, Marcel Roeloffzen, and Birgit Vogtenhuber. Packing Short Plane Spanning Trees in Complete Geometric Graphs. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.ISAAC.2016.9,
  author =	{Aichholzer, Oswin and Hackl, Thomas and Korman, Matias and Pilz, Alexander and Rote, G\"{u}nter and van Renssen, Andr\'{e} and Roeloffzen, Marcel and Vogtenhuber, Birgit},
  title =	{{Packing Short Plane Spanning Trees in Complete Geometric Graphs}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.9},
  URN =		{urn:nbn:de:0030-drops-67823},
  doi =		{10.4230/LIPIcs.ISAAC.2016.9},
  annote =	{Keywords: Geometric Graphs, Graph Packing, Plane Graphs, Minimum Spanning Tree, Bottleneck Edge}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.66
Approximation and Hardness of Token Swapping

Authors: Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Given a graph G=(V,E) with V={1,...,n}, we place on every vertex a token T_1,...,T_n. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that token T_i is on vertex i. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out any 2^{o(n)} algorithm under the ETH. This is matched with a simple 2^{O(n*log(n))} algorithm based on a breadth-first search in an auxiliary graph. We show one general 4-approximation and show APX-hardness. Thus, there is a small constant delta > 1 such that every polynomial time approximation algorithm has approximation factor at least delta. Our results also hold for a generalized version, where tokens and vertices are colored. In this generalized version each token must go to a vertex with the same color.
Cite as

Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno. Approximation and Hardness of Token Swapping. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{miltzow_et_al:LIPIcs.ESA.2016.66,
  author =	{Miltzow, Tillmann and Narins, Lothar and Okamoto, Yoshio and Rote, G\"{u}nter and Thomas, Antonis and Uno, Takeaki},
  title =	{{Approximation and Hardness of Token Swapping}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{66:1--66:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.66},
  URN =		{urn:nbn:de:0030-drops-64084},
  doi =		{10.4230/LIPIcs.ESA.2016.66},
  annote =	{Keywords: token swapping, minimum generator sequence, graph theory, NP-hardness, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.48
Congruence Testing of Point Sets in 4-Space

Authors: Heuna Kim and Günter Rote

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We give a deterministic O(n log n)-time algorithm to decide if two n-point sets in 4-dimensional Euclidean space are the same up to rotations and translations. It has been conjectured that O(n log n) algorithms should exist for any fixed dimension. The best algorithms in d-space so far are a deterministic algorithm by Brass and Knauer [Int. J. Comput. Geom. Appl., 2000] and a randomized Monte Carlo algorithm by Akutsu [Comp. Geom., 1998]. They take time O(n^2 log n) and O(n^(3/2) log n) respectively in 4-space. Our algorithm exploits many geometric structures and properties of 4-dimensional space.
Cite as

Heuna Kim and Günter Rote. Congruence Testing of Point Sets in 4-Space. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.SoCG.2016.48,
  author =	{Kim, Heuna and Rote, G\"{u}nter},
  title =	{{Congruence Testing of Point Sets in 4-Space}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.48},
  URN =		{urn:nbn:de:0030-drops-59409},
  doi =		{10.4230/LIPIcs.SoCG.2016.48},
  annote =	{Keywords: Congruence Testing Algorithm, Symmetry, Computational Geometry}
}
Document
DOI: 10.4230/LIPIcs.FUN.2016.19
Loopless Gray Code Enumeration and the Tower of Bucharest

Authors: Felix Herter and Günter Rote

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract
We give new algorithms for generating all n-tuples over an alphabet of m letters, changing only one letter at a time (Gray codes). These algorithms are based on the connection with variations of the Towers of Hanoi game. Our algorithms are loopless, in the sense that the next change can be determined in a constant number of steps, and they can be implemented in hardware. We also give another family of loopless algorithms that is based on the idea of working ahead and saving the work in a buffer.
Cite as

Felix Herter and Günter Rote. Loopless Gray Code Enumeration and the Tower of Bucharest. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{herter_et_al:LIPIcs.FUN.2016.19,
  author =	{Herter, Felix and Rote, G\"{u}nter},
  title =	{{Loopless Gray Code Enumeration and the Tower of Bucharest}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.19},
  URN =		{urn:nbn:de:0030-drops-58863},
  doi =		{10.4230/LIPIcs.FUN.2016.19},
  annote =	{Keywords: Tower of Hanoi, Gray code, enumeration, loopless generation}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.658
Shortest Path to a Segment and Quickest Visibility Queries

Authors: Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We show how to preprocess a polygonal domain with a fixed starting point s in order to answer efficiently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the well-known shortest-path-to-a-point query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a different generalization of shortest-path-to-a-point queries, which may be of independent interest: to report efficiently a shortest path from s to a query segment in the domain.
Cite as

Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie. Shortest Path to a Segment and Quickest Visibility Queries. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 658-673, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{arkin_et_al:LIPIcs.SOCG.2015.658,
  author =	{Arkin, Esther M. and Efrat, Alon and Knauer, Christian and Mitchell, Joseph S. B. and Polishchuk, Valentin and Rote, G\"{u}nter and Schlipf, Lena and Talvitie, Topi},
  title =	{{Shortest Path to a Segment and Quickest Visibility Queries}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{658--673},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.658},
  URN =		{urn:nbn:de:0030-drops-51474},
  doi =		{10.4230/LIPIcs.SOCG.2015.658},
  annote =	{Keywords: path planning, visibility, query structures and complexity, persistent data structures, continuous Dijkstra}
}
Document
DOI: 10.4230/DagSemProc.09111.6
Two Applications of Point Matching

Authors: Günter Rote

Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)

Abstract
The two following problems can be solved by a reduction to a minimum-weight bipartite matching problem (or a related network flow problem): a) Floodlight illumination: We are given $n$ infinite wedges (sectors, spotlights) that can cover the whole plane when placed at the origin. They are to be assigned to $n$ given locations (in arbitrary order, but without rotation) such that they still cover the whole plane. (This extends results of Bose et al. from 1997.) b) Convex partition: Partition a convex $m$-gon into $m$ convex parts, each part containing one of the edges and a given number of points from a given point set. (Garcia and Tejel 1995, Aurenhammer 2008)
Cite as

Günter Rote. Two Applications of Point Matching. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{rote:DagSemProc.09111.6,
  author =	{Rote, G\"{u}nter},
  title =	{{Two Applications of Point Matching}},
  booktitle =	{Computational Geometry},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9111},
  editor =	{Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.6},
  URN =		{urn:nbn:de:0030-drops-20292},
  doi =		{10.4230/DagSemProc.09111.6},
  annote =	{Keywords: Bipartite matching, least-squares}
}
Document
DOI: 10.4230/DagSemRep.372
Computational Geometry (Dagstuhl Seminar 03121)

Authors: Dan Halperin and Günter Rote

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Dan Halperin and Günter Rote. Computational Geometry (Dagstuhl Seminar 03121). Dagstuhl Seminar Report 372, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{halperin_et_al:DagSemRep.372,
  author =	{Halperin, Dan and Rote, G\"{u}nter},
  title =	{{Computational Geometry (Dagstuhl Seminar 03121)}},
  pages =	{1--6},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{372},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.372},
  URN =		{urn:nbn:de:0030-drops-152529},
  doi =		{10.4230/DagSemRep.372},
}
  • Refine by Author
  • 13 Rote, Günter
  • 1 Abrahamsen, Mikkel
  • 1 Ackerman, Eyal
  • 1 Agarwal, Pankaj K.
  • 1 Aichholzer, Oswin
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 1 Approximation
  • 1 Bipartite matching
  • 1 Bottleneck Edge
  • 1 Computational Geometry
  • 1 Congruence Testing Algorithm
  • Show More...

  • Refine by Type
  • 16 document

  • Refine by Publication Year
  • 4 2016
  • 4 2019
  • 2 2020
  • 1 2001
  • 1 2003
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact