Jean Cardinal

According to our database1, Jean Cardinal authored at least 110 papers between 1999 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.



In proceedings 
PhD thesis 


Online presence:



Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect.
Theor. Comput. Sci., 2020

Modular Subset Sum, Dynamic Strings, and Zero-Sum Sets.
CoRR, 2020

Dynamic Geometric Independent Set.
CoRR, 2020

Geometric Pattern Matching Reduces to k-SUM.
CoRR, 2020

Solving and Sampling with Many Solutions.
Algorithmica, 2020

Drawing Graphs as Spanners.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020

Sparse Regression via Range Counting.
Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

Competitive Online Search Trees on Trees.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Subquadratic encodings for point configurations.
J. Comput. Geom., 2019

Finding a Maximum-Weight Convex Set in a Chordal Graph.
J. Graph Algorithms Appl., 2019

Subquadratic Algorithms for Algebraic 3SUM.
Discret. Comput. Geom., 2019

Encoding 3SUM.
CoRR, 2019

Information-theoretic lower bounds for quantum sorting.
CoRR, 2019

Dynamic Graph Coloring.
Algorithmica, 2019

Flip Distances Between Graph Orientations.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2019

Chirotopes of Random Points in Space are Realizable on a Small Integer Grid.
Proceedings of the 31st Canadian Conference on Computational Geometry, 2019

Three-Coloring Three-Dimensional Uniform Hypergraphs.
Proceedings of the 31st Canadian Conference on Computational Geometry, 2019

Topological drawings of complete bipartite graphs.
J. Comput. Geom., 2018

Intersection Graphs of Rays and Grounded Segments.
J. Graph Algorithms Appl., 2018

A Note on Flips in Diagonal Rectangulations.
Discret. Math. Theor. Comput. Sci., 2018

Arc diagrams, flip distances, and Hamiltonian triangulations.
Comput. Geom., 2018

On the Diameter of Tree Associahedra.
Electron. J. Comb., 2018

Recognition and Complexity of Point Visibility Graphs.
Discret. Comput. Geom., 2017

Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems.
Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

Subquadratic Algorithms for Algebraic Generalizations of 3SUM.
Proceedings of the 33rd International Symposium on Computational Geometry, 2017

Reconstructing Point Set Order Types from Radial Orderings.
Int. J. Comput. Geom. Appl., 2016

On the shelling antimatroids of split graphs.
Electron. Notes Discret. Math., 2016

Ramsey-type theorems for lines in 3-space.
Discret. Math. Theor. Comput. Sci., 2016

Solving k-SUM Using Few Linear Queries.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Computational Geometry Column 62.
SIGACT News, 2015

Cannibal Animal Games: a new variant of Tic-Tac-Toe.
J. Inf. Process., 2015

The Complexity of Simultaneous Geometric Graph Embedding.
J. Graph Algorithms Appl., 2015

On Universal Point Sets for Planar Graphs.
J. Graph Algorithms Appl., 2015

On the Decision Tree Complexity of $k$-SUM.
CoRR, 2015

Covering Partial Cubes with Zones.
Electron. J. Comb., 2015

Hitting All Maximal Independent Sets of a Bipartite Graph.
Algorithmica, 2015

Making Octants Colorful and Related Covering Decomposition Problems.
SIAM J. Discret. Math., 2014

The Price of Connectivity for Vertex Cover.
Discret. Math. Theor. Comput. Sci., 2014

Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane.
Discret. Math. Theor. Comput. Sci., 2014

General Position Subsets and Independent Hyperplanes in d-Space.
CoRR, 2014

Draining a polygon - or - rolling a ball out of a polygon.
Comput. Geom., 2014

Reconstructing Point Set Order Typesfrom Radial Orderings.
Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

Making Triangles Colorful.
J. Comput. Geom., 2013

The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs.
J. Comb. Optim., 2013

Helly Numbers of Polyominoes.
Graphs Comb., 2013

Coloring and Guarding Arrangements.
Discret. Math. Theor. Comput. Sci., 2013

The Clique Problem in Ray Intersection Graphs.
Discret. Comput. Geom., 2013

Coloring planar homothets and three-dimensional hypergraphs.
Comput. Geom., 2013

Non-crossing matchings of points with geometric objects.
Comput. Geom., 2013

Sorting under partial information (without the ellipsoid algorithm).
Comb., 2013

Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles.
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane.
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

On Generalized Comparison-Based Sorting Problems.
Proceedings of the Space-Efficient Data Structures, 2013

Minimum Entropy Combinatorial Optimization Problems.
Theory Comput. Syst., 2012

Approximating vertex cover in dense hypergraphs.
J. Discrete Algorithms, 2012

The Price of Connectivity for Vertex Cover: Perfect, Near-Perfect and Critical Graphs.
Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2012

Algorithmic Folding Complexity.
Graphs Comb., 2011

Colorful Strips.
Graphs Comb., 2011

Approximating Subdense Instances of Covering Problems.
Electron. Notes Discret. Math., 2011

The Stackelberg Minimum Spanning Tree Game.
Algorithmica, 2011

Connected vertex covers in dense graphs.
Theor. Comput. Sci., 2010

Non-cooperative facility location and covering games.
Theor. Comput. Sci., 2010

An Efficient Algorithm for Partial Order Production.
SIAM J. Comput., 2010

Decomposition of Multiple Coverings into More Parts.
Discret. Comput. Geom., 2010

Minimum sum edge colorings of multicycles.
Discret. Appl. Math., 2010

Highway hull revisited.
Comput. Geom., 2010

Improved approximation bounds for edge dominating set in dense graphs.
Theor. Comput. Sci., 2009

Pricing Geometric Transportation Networks.
Int. J. Comput. Geom. Appl., 2009

Coloring Geometric Range Spaces.
Discret. Comput. Geom., 2009

Detecting all regular polygons in a point set
CoRR, 2009

Empty region graphs.
Comput. Geom., 2009

Algorithmic Folding Complexity.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Relaxed Gabriel Graphs.
Proceedings of the 21st Annual Canadian Conference on Computational Geometry, 2009

Minimum entropy orientations.
Oper. Res. Lett., 2008

Minimum entropy coloring.
J. Comb. Optim., 2008

Chromatic Edge Strength of Some Multigraphs.
Electron. Notes Discret. Math., 2008

Set Covering Problems with General Objective Functions
CoRR, 2008

Local properties of geometric graphs.
Comput. Geom., 2008

Optimal location of transportation devices.
Comput. Geom., 2008

Tight Results on Minimum Entropy Set Cover.
Algorithmica, 2008

Efficient Rate-Distortion Optimized Media Streaming for Tree-Structured Packet Dependencies.
IEEE Trans. Multim., 2007

Moving Walkways, Escalators, and Elevators
CoRR, 2007

Branch and bound algorithms for rate-distortion optimized media streaming.
IEEE Trans. Multim., 2006

Juggling with Pattern Matching.
Theory Comput. Syst., 2006

Selfish Service Installation in Networks.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Constructing Dependency Trees for Rate-Distortion Optimized Media Streaming.
Proceedings of the 2006 IEEE International Conference on Acoustics Speech and Signal Processing, 2006

Proceedings of the Computers and Games, 5th International Conference, 2006

Designing small keyboards is hard.
Theor. Comput. Sci., 2005

Dynamic programming algorithm for rate-distortion optimized media streaming.
Proceedings of the 2005 International Conference on Image Processing, 2005

Region counting graphs.
Proceedings of the (Informal) Proceedings of the 21st European Workshop on Computational Geometry, 2005

A Tight Analysis of the Maximal Matching Heuristic.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

Region Counting Distances and Region Counting Circles.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

Entropy-constrained index assignments for multiple description quantizers.
IEEE Trans. Signal Process., 2004

Reconciliation of a quantum-distributed Gaussian key.
IEEE Trans. Inf. Theory, 2004

On minimum entropy graph colorings.
Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

On the Complexity of Rate-Distortion Optimal Streaming of Packetized Media.
Proceedings of the 2004 Data Compression Conference (DCC 2004), 2004

Lazy Algorithms for Dynamic Closest Pair with Arbitary Distance Measures.
Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, 2004

Tree-Structured Multiple Description Coding.
J. VLSI Signal Process., 2003

Construction of a shared secret key using continuous variables.
Proceedings of the Proceedings 2003 IEEE Information Theory Workshop, 2003

Compression of side information.
Proceedings of the 2003 IEEE International Conference on Multimedia and Expo, 2003

Multistage index assignments for M-description coding.
Proceedings of the 2003 International Conference on Image Processing, 2003

Complexity-constrained tree-structured vector quantizers.
Signal Process., 2002

Local optimization of index assignments for multiple description coding.
Proceedings of the 11th European Signal Processing Conference, 2002

Fast fractal compression of greyscale images.
IEEE Trans. Image Process., 2001

Design of asymmetric tree-structured multiple description source codes.
Proceedings of the Fourth IEEE Workshop on Multimedia Signal Processing, 2001

Design of Tree-Structured Multiple Description Vector Quantizers.
Proceedings of the Data Compression Conference, 2001

Multipath tree-structured vector quantizers.
Proceedings of the 10th European Signal Processing Conference, 2000

Tree-Based Search for ECVQ.
Proceedings of the Data Compression Conference, 2000

Fast Search for Entropy-Constrained VQ.
Proceedings of the 1oth International Conference on Image Analysis and Processing (ICIAP 1999), 1999