20 citations · 66 across the 52 of their papers we have counts for
6 papers · 1 filter
Minimum Sum Vertex Cover via Minimum Vertex Cover
Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +2
The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered.…
Shortest Beer Path Queries in Outerplanar Graphs
Joyce Bacic, Saeed Mehrabi, Michiel Smid
A \emph{beer graph} is an undirected graph , in which each edge has a positive weight and some vertices have a beer store. A \emph{beer path} between two vertices and in…
An Instance-Based Algorithm for Deciding the Bias of a Coin
Luís Fernando Schultz Xavier da Silveira, Michiel Smid
Let and be real numbers, and let be a coin that comes up heads with an unknown probability , such that . We present an algorithm that, o…
Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles
Timothy M. Chan, Yakov Nekrich, Michiel Smid
In this paper we study two geometric data structure problems in the special case when input objects or queries are fat rectangles. We show that in this case a significant improveme…
An Ω(n log n) lower bound for computing the sum of even-ranked elements
Marc Mörig, Dieter Rautenbach, Michiel Smid +1
Given a sequence A of 2n real numbers, the Even-Rank-Sum problem asks for the sum of the n values that are at the even positions in the sorted order of the elements in A. We prove…
Range Mode and Range Median Queries on Lists and Trees
Danny Krizanc, Pat Morin, Michiel Smid
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequ…