13 citations · 25 across the 18 of their papers we have counts for
10 papers · 1 filter
Dynamic Geometric Independent Set
Sujoy Bhore, Jean Cardinal, John Iacono +1
We present fully dynamic approximation algorithms for the Maximum Independent Set problem on several types of geometric objects: intervals on the real line, arbitrary axis-aligned…
Drawing Graphs as Spanners
Oswin Aichholzer, Manuel Borrazzo, Prosenjit Bose +4
We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph , the goal is to construct a straight-line drawing of in the plane…
Competitive Online Search Trees on Trees
Prosenjit Bose, Jean Cardinal, John Iacono +2
We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tre…
Sparse Regression via Range Counting
Jean Cardinal, Aurélien Ooms
The sparse regression problem, also known as best subset selection problem, can be cast as follows: Given a set of points in , a point , an…
Encoding 3SUM
Sergio Cabello, Jean Cardinal, John Iacono +3
We consider the following problem: given three sets of real numbers, output a word-RAM data structure from which we can efficiently recover the sign of the sum of any triple of num…
Finding a Maximum-Weight Convex Set in a Chordal Graph
Jean Cardinal, Jean-Paul Doignon, Keno Merckx
We consider a natural combinatorial optimization problem on chordal graphs, the class of graphs with no induced cycle of length four or more. A subset of vertices of a chordal grap…