2010

Complexity Theory

• Milling a Graph with Turn Costs: A Parametrized Complexity Perspective
  In WG, Lecture Notes in Computer Science, Volume 6410, Pages 123-134, 2010.
  Mike Fellows, Panos Giannopoulos, Christian Knauer, Christophe Paul, Frances A. Rosamond, Sue Whitesides, Nathan Yu
  [doi]
  [bibtex]

Computational Geometry

• Can We Compute the Similarity between Surfaces?
  Discrete and Computational Geometry, Volume 43 (1), Pages 78–99, 2010.
  Helmut Alt, Maike Buchin
  [bibtex]

• Computing the depth of an arrangement of axis-aligned rectangles in parallel
  In Proceedings of the 26th European Workshop on Computational Geometry (EuroCG), Pages 33–36, Dortmund, Germany, March 2010.
  Helmut Alt, Ludmila Scharf
  [bibtex]

• Largest Inscribed Rectangles in Simple Polygons
  In EuroCG'10, Pages 201-204, 2010.
  Christian Knauer, Lena Schlipf, Jens Schmidt, Hans Tiwary
  [bibtex]

• Hardness of discrepancy computation and epsilon-net verification in high dimension
  In Proccedings of the 26 th European Workshop on Computational Geometry (EuroCG), Dortmund, Germany, March 2010.
  Panos Giannopoulos, Christian Knauer, Magnus Wahlström, Daniel Werner
  [bibtex]

Geometric Optimization Problems

• Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town?
  CoRR, Volume abs/1009.5628, 2010.
  Erik D. Demaine, Sándor P.Fekete, Günter Rote, Nils Schweer, Daria Schymura, Mariano Zelke
  [Eprint:arXiv:1009.5628]
  [bibtex]

Geometric Shape and Pattern Matching

• Probabilistic Matching of Planar Regions
  Computational Geometry, Theory and Applications (CGTA), Volume 43 (2), Pages 99–114, 2010.
  Helmut Alt, Ludmila Scharf, Daria Schymura
  Special Issue on the 24th European Workshop on Computational Geometry (EuroCG'08)
  view at ScienceDirect
  [bibtex]

• Computing the Discrete Fréchet Distance with Imprecise Input
  In Proceedings of the 26th European Workshop on Computational Geometry (EuroCG), Pages 13–16, Dortmund, Germany, 2010.
  Hee-Kap Ahn, Christian Knauer, Marc Scherfenberg, Lena Schlipf, Antoine Vigneron
  [bibtex] [pdf]

• Computing the Discrete Fréchet Distance with Imprecise Input
  In Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC 2010), Lecture Notes in Computer Science, Volume 6507, Pages 422–433, Editor(s) Cheong, Otfried and Chwa, Kyung-Yong and Park, Kunsoo, Springer-Verlag, Berlin/Heidelberg, Germany, 2010.
  Hee-Kap Ahn, Christian Knauer, Marc Scherfenberg, Lena Schlipf, Antoine Vigneron
  [bibtex] [pdf]

• An upper bound on the volume of the symmetric difference of a body and a congruent copy
  CoRR, Volume abs/1010.2446, 2010.
  Daria Schymura
  [Eprint:arXiv:1010.2446]
  [bibtex]

Graph Theory and Algorithms

• Construction Sequences and Certifying 3-Connectedness
  In 27th International Symposium on Theoretical Aspects of Computer Science (STACS'10), Nancy, France, 2010.
  Jens Schmidt
  http://page.mi.fu-berlin.de/jeschmid/pub
  [bibtex]

• On Wiener Index of Graphs and Their Line Graphs
  MATCH Communications in Mathematical and in Computer Chemistry, Volume 64 (3), Pages 683–698, 2010.
  Nathann Cohen, Darko Dimitrov, Roi Krakovski, Vida Vukašinović, Riste Škrekovski
  [bibtex]

• A Linear-Time Certifying Triconnnectivity Algorithm for Hamiltonian Graphs
  Algorithmica, 2010.
  A. Elmasry, K. Mehlhorn, Jens Schmidt
  [bibtex] [pdf]

• Construction Sequences and Certifying 3-Connectivity
  Algorithmica, 2010.
  Jens Schmidt
  [bibtex] [pdf]

• Contractions, Removals and Certifying 3-Connectivity in Linear Time
  Freie Universität Berlin, Germany, 2010.
  Jens Schmidt
  [bibtex]

Logic

• Directed free pseudospaces
  Journal of Symbolic Logic, Volume 75 (4), Pages 1176–1198, 2010.
  Romain Grunert
  [bibtex]