35 citations · 62 across the 7 of their papers we have counts for
7 papers
Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town?
Erik D. Demaine, Sandor P. Fekete, Guenter Rote +3
An n-town, for a natural number n, is a group of n buildings, each occupying a distinct position on a 2-dimensional integer grid. If we measure the distance between two buildings a…
Weighted Matching in the Semi-Streaming Model
Mariano Zelke
We reduce the best known approximation ratio for finding a weighted matching of a graph using a one-pass semi-streaming algorithm from 5.828 to 5.585. The semi-streaming model forb…
Polyhedral tori with minimal coordinates
Stefan Hougardy, Frank H. Lutz, Mariano Zelke
We give explicit realizations with small integer coordinates for all triangulated tori with up to 12 vertices. In particular, we provide coordinate-minimal realizations in general…
Optimal Per-Edge Processing Times in the Semi-Streaming Model
Mariano Zelke
We present semi-streaming algorithms for basic graph problems that have optimal per-edge processing times and therefore surpass all previous semi-streaming algorithms for these tas…
k-Connectivity in the Semi-Streaming Model
Mariano Zelke
We present the first semi-streaming algorithms to determine k-connectivity of an undirected graph with k being any constant. The semi-streaming model for graph algorithms was intro…
Surface realization with the intersection edge functional
Stefan Hougardy, Frank H. Lutz, Mariano Zelke
Deciding realizability of a given polyhedral map on a (compact, connected) surface belongs to the hard problems in discrete geometry, from the theoretical, the algorithmic, and the…