conf.bib

@comment{{This file has been generated by bib2bib 1.99}}

@comment{{Command line: bib2bib -s year -r -c '$type = "INPROCEEDINGS"' bibtexfiles/secollet.bib}}

@inproceedings{CI24a,
  abstract = { Dijkstra's algorithm is the standard method for computing shortest paths on
arbitrary graphs. However, it is slow for large graphs, taking at least linear
time. It has been long known that for real world road networks, creating a
hierarchy of well-chosen shortcuts allows fast distance and path computation,
with exact distance queries seemingly being answered in logarithmic time.
However, these methods were but heuristics until the work of Abraham et
al.~[JACM 2016], where they defined a graph parameter called highway dimension
which is constant for real-world road networks, and showed that in graphs of
constant highway dimension, a shortcut hierarchy exists that guarantees
shortest distance computation takes $O(\log (U+V))$ time and $O(V \log (U+V))$
space, where $U$ is the ratio of the smallest to largest edge, and $V$ is the
number of vertices. The problem is that they were unable to efficiently compute
the hierarchy of shortcuts. Here we present a simple and efficient algorithm to
compute the needed hierarchy of shortcuts in time and space $O(V \log (U+V))$,
as well as supporting updates in time $O( \log (U+V))$.},
  author = {S. Collette and J. Iacono},
  booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'24)},
  title = {Distances and shortest paths on graphs of bounded highway dimension:
  simple, fast, dynamic},
  year = {2024}
}

@inproceedings{BCFL12b,
  author = {P. Bose and S. Collette and R. Fagerberg and S. Langerman},
  title = {De-amortizing Binary Search Trees},
  booktitle = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012)},
  series = {LNCS},
  year = {2012}
}

@inproceedings{CIL12a,
  abstract = {It is shown how to enhance any data structure in the pointer model to make it confluently persistent, with efficient query and update times and limited space overhead. Updates are performed in $O(\log n)$ amortized time, and following a pointer takes $O(\log c \log n)$ time where $c$ is the in-degree of a node in the data structure. In particular, this proves that confluent persistence can be achieved at a logarithmic cost in the bounded in-degree model used widely in previous work. This is a $O(n/\log n)$-factor improvement over the previous known transform to make a data structure confluently persistent.},
  author = {S. Collette and
               J. Iacono and
               S. Langerman},
  title = {Confluent persistence revisited},
  booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'12)},
  year = {2012},
  pages = {593-601}
}

@inproceedings{ACCDDDFHHLSST09b,
  author = {G. Aloupis and J. Cardinal and S. Collette and E. D. Demaine and M. L. Demaine and
M. Dulieu and R. Fabila-Monroy and V. Hart and F. Hurtado and S. Langerman and M. Saumell and
C. Seara and P. Taslakian},
  series = {LNCS},
  title = {Matching Points with Things},
  booktitle = {Proceedings of the 8th Latin American Theoretical Informatics (LATIN'10)},
  year = {2010},
  note = {12 pages}
}

@inproceedings{ACCIKLSST09c,
  author = {G. Aloupis and J. Cardinal and S. Collette and S. Imahori and M. Korman and S. Langerman and O. Schwartz and S. Smorodinsky and P. Taslakian},
  series = {LNCS},
  booktitle = {Proceedings of the 8th Latin American Theoretical Informatics (LATIN'10)},
  title = {Colorful Strips},
  year = {2010},
  note = {12 pages}
}

@inproceedings{ACCLOR08a,
  abstract = {We prove that for every centrally symmetric convex polygon Q, there exists a constant alpha such that any alpha*k-fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Toth (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery lifetime.},
  author = {G. Aloupis and J. Cardinal and S. Collette and S. Langerman and D. Orden and P. Ramos},
  booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'09)},
  title = {Decomposition of Multiple Coverings into More Parts},
  note = {9 pages},
  year = {2009}
}

@inproceedings{ACDDEFLOPRSW08a,
  abstract = {In this paper we propose novel algorithms for reconfiguring
cube-style modular
robots that are composed of n identical atoms.  Each atom has the
shape of a unit cube and can expand/contract each face by half a unit,
as well as attach/detach to faces of neighboring atoms.  For universal
reconfiguration, it is necessary for atoms to be arranged in 2x2x2 modules.  We respect certain physical constraints: each module reaches at most unit velocity and (via expansion) can
displace at most one other module.  
We only require one of the modules
to be able to store a map of the target configuration.

Reconfiguration via our algorithms involves a total of O(n^2) such
atom operations, but is performed in O(n) parallel steps.  This
improves on previous reconfiguration algorithms, which either use
O(n^2) parallel steps or do not respect the constraints mentioned above.  In fact, in the setting
considered, our algorithms are worst-case optimal. A further advantage
by our algorithmsis that reconfiguration can take place within the union
of the source and target configurations.},
  author = {G. Aloupis and S. Collette and M. Damian and E. Demaine and D. El-Khechen and R. Flatland and S. Langerman and J. O'Rourke and V. Pinciu and S. Ramaswami and V. Sacristan and S. Wuhrer},
  booktitle = {Proceedings of the Workshop on the Algorithmic Foundations of Robotics (WAFR'08)},
  note = {18 pages},
  title = {Realistic Reconfiguration of Crystalline (and Telecube) Robots},
  year = {2008}
}

@inproceedings{BCCS08b,
  abstract = {Let C be a compact and convex set in the plane that contains the origin 
in its interior, and let S be a finite set of points in the plane. 
The Delaunay graph DG_C(S) of S is defined to be the dual of the 
Voronoi diagram of S with respect to the convex distance function 
defined by C. We prove that DG_C(S) is a t-spanner for S, 
for some constant t that depends only on the shape of the set C. 
Thus, for any two points p and q in S, the graph DG_C(S) 
contains a path between p and q whose Euclidean length is at most 
t times the Euclidean distance between p and q.},
  author = {P. Bose and P. Carmi and S. Collette and M. Smid},
  booktitle = {Proceedings of the International Symposium on Algorithms and Computation (ISAAC 2008)},
  note = {12 pages},
  series = {LNCS},
  volume = {5369},
  title = {On the Stretch Factor of Convex Delaunay Graphs},
  year = {2008}
}

@inproceedings{ACDLSW08a,
  abstract = {We consider a model of reconfigurable robot, introduced and prototyped by the robotics community. The robot consists of independently manipulable unit-square atoms that can extend/contract arms on each side and attach/detach from neighbors. The optimal worst-case number of sequential moves required to transform one connected configuration to another was shown to be Theta(n) at ISAAC 2007. However, in principle, atoms can all move simultaneously. We develop a parallel algorithm for reconfiguration that runs in only O(log n) parallel steps, although the total number of operations increases slightly to Theta(n log n). 
The result is the first (theoretically) almost-instantaneous universally reconfigurable robot built from simple units.},
  author = {G. Aloupis and S. Collette and E. D. Demaine and S. Langerman and V. Sacristan and S. Wuhrer},
  booktitle = {Proceedings of the International Symposium on Algorithms and Computation (ISAAC 2008)},
  note = {12 pages},
  series = {LNCS},
  volume = {5369},
  title = {Reconfiguration of Cube-Style Modular Robots Using {O}(log n) Parallel Moves},
  year = {2008}
}

@inproceedings{ACCLS07c,
  abstract = {We study several coloring problems for geometric range-spaces. In
addition to their theoretical interest, some of these problems
arise in sensor networks. Given a set of points in R^2
or R^3, we want to color them such that every region of
a certain family (e.g., every disk containing at least a certain
number of points) contains points of many different colors. In
this paper, we think of the number of colors and the number of
points as functions of k. Obviously, for a fixed k using k
colors, it is not always possible to ensure that every region
containing k points has all colors present. Thus, we introduce
two types of relaxations: either we allow the number of colors to
increase to c(k), or we require that the number of points in
each region increases to p(k).

Symmetrically, given a finite set of regions  in R^2 or
R^3, we want to color them such that every point
covered by a sufficiently large number of regions is contained in
regions of k different colors.  This requires the number of
covering regions or the number of allowed colors to be greater
than k.

The goal of this paper is to bound these two functions for several
types of region families, such as halfplanes, halfspaces, disks
and pseudo-disks. We improve and generalize previous results of
Pach, Tardos and Toth on decompositions of space coverings.},
  author = {G. Aloupis and J. Cardinal and S. Collette and S. Langerman and S. Smorodinsky},
  series = {LNCS},
  volume = {4957},
  booktitle = {Proceedings of the 8th Latin American Theoretical Informatics (LATIN'08)},
  title = {Coloring Geometric Range Spaces},
  year = {2008},
  doi = {10.1007/978-3-540-78773-0_13},
  note = {12 pages}
}

@inproceedings{CDILM07,
  abstract = {A data structure is presented for point location in convex planar
subdivisions when the distribution of queries is known in advance.
The data structure has an expected query time that differs from the optimal one by only lower order terms  in the linear comparison tree model. },
  author = {S. Collette and V. Dujmovi\'c and J. Iacono and S. Langerman and P. Morin},
  booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'08)},
  title = {Distribution-sensitive point location in convex subdivisions},
  year = {2008},
  note = {11 pages}
}

@inproceedings{ACDDFLORSW07b,
  abstract = {In this paper we propose a novel algorithm that, given a source robot S and a target robot T, reconfigures S into T.  Both S and T are robots composed of n atoms arranged in 2 x 2 x 2 meta-modules.  The reconfiguration involves a total of O(n) atom operations (expand, contract, attach, detach) and is performed in O(n) parallel steps.  This improves on previous reconfiguration algorithms, which require O(n^2) parallel steps.  Our algorithm is in place; that is, the reconfiguration takes place within the union of the bounding boxes of the source and target robots. We show that the algorithm can also be implemented in a synchronous, distributed fashion.},
  author = {G. Aloupis and S. Collette and M. Damian and E. D. Demaine and R. Flatland and S. Langerman and J. O'Rourke and S. Ramaswami and V. Sacristan and S. Wuhrer},
  booktitle = {Proceedings of the International Symposium on Algorithms and Computation (ISAAC 2007)},
  note = {14 pages},
  series = {LNCS},
  volume = {4835},
  title = {Linear Reconfiguration of Cube-Style Modular Robots},
  doi = {10.1007/978-3-540-77120-3_20},
  year = {2007}
}

@inproceedings{CCG07,
  abstract = {We investigate the global scheduling of sporadic, implicit
deadline, real-time task systems on identical multiprocessor
platforms. We provide a task model which integrates
work-limited job parallelism. For work-limited parallelism,
we prove that the time-complexity of deciding if a task set
is feasible is linear relatively to the number of (sporadic)
tasks for a fixed number of processors. Based on this proof,
we propose an optimal scheduling algorithm. Moreover, we
provide an exact feasibility utilization bound.},
  author = {S. Collette and L. Cucu and J. Goossens},
  booktitle = {Proceedings of the 15th International Conference on Real-Time and Network systems ({RTNS'2007})},
  note = {6 pages},
  title = {Algorithm and complexity for the global scheduling of sporadic tasks on multiprocessors with work-limited parallelism},
  year = {2007}
}

@inproceedings{ACCL06,
  abstract = {We analyze a new popular video-game called Lumines, 
which was developed by Sony for the PSP platform.  It involves a sequence of 
bichromatic 2x2 blocks that fall in a grid and must be shifted or rotated by 
the player before they land.  Patterns of monochromatic 2x2 blocks in the 
terrain are regularly deleted.  The primary goal is to contain the terrain 
within a fixed height and, if possible, clear the grid.
We deal with questions such as the following: Can the game be played 
indefinitely? Can all terrains be eliminated?  We examine how answers to 
these questions depend on the size of the grid and the rate at which 
blocks are deleted.},
  author = {G. Aloupis and J. Cardinal and S. Collette and S. Langerman},
  booktitle = {Proceedings of the 5th International Conference on Computers and Games (CG 2006)},
  pages = {190--199},
  series = {LNCS},
  volume = {4630},
  pdf = {http://www.ulb.ac.be/di/algo/secollet/papers/accl06.pdf},
  doi = {10.1007/978-3-540-75538-8_17},
  title = {Lumines Strategies},
  year = {2007}
}

@inproceedings{CRS06,
  abstract = {Rushhour  is a sliding block game where blocks represent cars stuck 
  in a traffic jam on a 6x6 board. The goal of the game is to allow 
  one of the cars (the target car) to exit this traffic jam by moving 
  the other cars out of its way.  In this paper, we study the
  problem of finding difficult initial configurations for this game.
  An initial configuration is difficult if the number of car moves
  necessary to exit the target car is high.  To solve the problem, we
  model the game in propositional logic and we apply symbolic
  model-checking techniques to study the huge graph of configurations
  that underlies the game.  On the positive side, we show that this
  huge graph (containing 3.6x10^10 vertices) can be
  completely analyzed using symbolic model-checking techniques with
  reasonable computing resources. We have classified every possible
  initial configuration of the game according to the length of its
  shortest solution. On the negative side, we prove a general theorem
  that shows some limits of symbolic model-checking methods for board
  games. This result explains why some natural modeling of board games
  leads to the explosion of the size of symbolic data-structures.},
  author = {S. Collette and J.-F. Raskin and F. Servais},
  booktitle = {Proceedings of the 5th International Conference on Computers and Games (CG 2006)},
  pages = {220-233},
  series = {LNCS},
  volume = {4630},
  pdf = {http://www.ulb.ac.be/di/algo/secollet/papers/crs06.pdf},
  doi = {10.1007/978-3-540-75538-8_20},
  title = {On the Symbolic Computation of the Hardest Configurations of the RUSH HOUR Game},
  year = {2007}
}

@comment{{This file has been generated by bib2bib 1.99}}

@comment{{Command line: bib2bib -s year -r -c '$type = "INPROCEEDINGS"' bibtexfiles/secollet-future.bib}}