Publications (41)
Finding a Maximum-Weight Convex Set in a Chordal Graph
Jean Cardinal, Jean-Paul Doignon, Keno Merckx
Competitive Online Search Trees on Trees
Prosenjit Bose, Jean Cardinal, John Iacono +2
The paper introduces an online data structure for searching in tree‑shaped spaces that extends the binary search tree model and achieves an O(log log n) competitive ratio using a n…
Minimum Entropy Combinatorial Optimization Problems
Jean Cardinal, Samuel Fiorini, Gwenaël Joret
Helly Numbers of Polyominoes
Jean Cardinal, Hiro Ito, Matias Korman +1
Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles
Andrei Asinowski, Jean Cardinal, Nathann Cohen +9
Detecting all regular polygons in a point set
Greg Aloupis, Jean Cardinal, Sebastien Collette +2
Dynamic Graph Coloring
Luis Barba, Jean Cardinal, Matias Korman +4
On Universal Point Sets for Planar Graphs
Jean Cardinal, Michael Hoffmann, Vincent Kusters
Minimum Sum Edge Colorings of Multicycles
Jean Cardinal, Vlady Ravelomanana, Mario Valencia-Pabon
Coloring and Guarding Arrangements
Prosenjit Bose, Jean Cardinal, Sébastien Collette +4
The Stackelberg Minimum Spanning Tree Game
Jean Cardinal, Erik D. Demaine, Samuel Fiorini +4
Approximating Vertex Cover in Dense Hypergraphs
Jean Cardinal, Marek Karpinski, Richard Schmied +1
The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs
Jean Cardinal, Erik D. Demaine, Samuel Fiorini +3
Solving $k$-SUM using few linear queries
Jean Cardinal, John Iacono, Aurélien Ooms
The Price of Connectivity for Vertex Cover
Eglantine Camby, Jean Cardinal, Samuel Fiorini +1
Making Triangles Colorful
Jean Cardinal, Kolja Knauer, Piotr Micek +1
Recognition and Complexity of Point Visibility Graphs
Jean Cardinal, Udo Hoffmann
An Efficient Algorithm for Partial Order Production
Jean Cardinal, Samuel Fiorini, Gwenaël Joret +2
Encoding 3SUM
Sergio Cabello, Jean Cardinal, John Iacono +3
Approximating Subdense Instances of Covering Problems
Jean Cardinal, Marek Karpinski, Richard Schmied +1
On the Diameter of Tree Associahedra
Jean Cardinal, Stefan Langerman, Pablo Pérez-Lantero
Making Octants Colorful and Related Covering Decomposition Problems
Jean Cardinal, Kolja Knauer, Piotr Micek +1
Set Covering Problems with General Objective Functions
Jean Cardinal, Christophe Dumeunier
Subquadratic Algorithms for Algebraic Generalizations of 3SUM
Luis Barba, Jean Cardinal, John Iacono +3
Information-theoretic lower bounds for quantum sorting
Jean Cardinal, Gwenaël Joret, Jérémie Roland
Covering Partial Cubes with Zones
Jean Cardinal, Stefan Felsner
Coloring Planar Homothets and Three-Dimensional Hypergraphs
Jean Cardinal, Matias Korman
Subquadratic Encodings for Point Configurations
Jean Cardinal, Timothy M. Chan, John Iacono +2
The Complexity of Simultaneous Geometric Graph Embedding
Jean Cardinal, Vincent Kusters
Topological Drawings of Complete Bipartite Graphs
Jean Cardinal, Stefan Felsner
Arc diagrams, flip distances, and Hamiltonian triangulations
Jean Cardinal, Michael Hoffmann, Vincent Kusters +2
The Clique Problem in Ray Intersection Graphs
Sergio Cabello, Jean Cardinal, Stefan Langerman
Flip distances between graph orientations
Oswin Aichholzer, Jean Cardinal, Tony Huynh +4
Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems
Jean Cardinal, Jerri Nummenpalo, Emo Welzl
Sorting under Partial Information (without the Ellipsoid Algorithm)
Jean Cardinal, Samuel Fiorini, Gwenaël Joret +2
General Position Subsets and Independent Hyperplanes in d-Space
Jean Cardinal, Csaba D. Tóth, David R. Wood
Cannibal Animal Games: a new variant of Tic-Tac-Toe
Jean Cardinal, Sébastien Collette, Hiro Ito +4
Minimum Entropy Orientations
Jean Cardinal, Samuel Fiorini, Gwenaël Joret
Highway Hull Revisited
Greg Aloupis, Jean Cardinal, Sebastien Collette +4
Intersection Graphs of Rays and Grounded Segments
Jean Cardinal, Stefan Felsner, Tillmann Miltzow +2
Hitting all Maximal Independent Sets of a Bipartite Graph
Jean Cardinal, Gwenaël Joret