215 citations · 441 across the 50 of their papers we have counts for
69 papers
Combinatorial generation via permutation languages. V. Acyclic orientations
Jean Cardinal, Hung P. Hoang, Arturo Merino +2
In 1993, Savage, Squire, and West described an inductive construction for generating every acyclic orientation of a chordal graph exactly once, flipping one arc at a time. We provi…
Improved Algebraic Degeneracy Testing
Jean Cardinal, Micha Sharir
In the classical linear degeneracy testing problem, we are given real numbers and a -variate linear polynomial , for some constant , and have to determine whether ther…
The rotation distance of brooms
Jean Cardinal, Lionel Pournin, Mario Valencia-Pabon
The associahedron of a graph has the property that its vertices can be thought of as the search trees on and its edges as the rotations between two search…
Inapproximability of shortest paths on perfect matching polytopes
Jean Cardinal, Raphael Steiner
We consider the computational problem of finding short paths in the skeleton of the perfect matching polytope of a bipartite graph. We prove that unless , there is no polynom…
Subquadratic Algorithms for Some \textsc{3Sum}-Hard Geometric Problems in the Algebraic Decision Tree Model
Boris Aronov, Mark de Berg, Jean Cardinal +3
We present subquadratic algorithms in the algebraic decision-tree model for several \textsc{3Sum}-hard geometric problems, all of which can be reduced to the following question: Gi…
Worst-Case Efficient Dynamic Geometric Independent Set
Jean Cardinal, John Iacono, Grigorios Koumoutsos
We consider the problem of maintaining an approximate maximum independent set of geometric objects under insertions and deletions. We present data structures that maintain a consta…