1 citations · 2 across the 13 of their papers we have counts for
4 papers · 1 filter
Geometric Graph Representations via Compact SAT Encodings
L. Sunil Chandran, Rishikesh Gajjala, Suraj Kumar Sahoo +1
We present compact SAT encodings and certifying exact solvers for boxicity and cubicity. The boxicity of a graph is the minimum dimension in which it is the intersection graph of a…
Towards Learning-Guided Discovery of Extremal Geometric Constructions: A PatternBoost Study
Deepak Ajwani, Paula Carroll, Rishikesh Gajjala +5
Extremal constructions play a central role in the design and analysis of algorithms. Integrality-gap instances expose the limitations of relaxations, while hard configurations reve…
Tight Approximation Thresholds for Geometric Stabbing
Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray
We study geometric covering problems: stabbing axis-parallel squares and cubes by coordinate hyperplanes, stabbing horizontal segments by horizontal and vertical lines, and transve…
Counterexamples to Wegner's Conjecture for Rectangles
Deepak Ajwani, Rishikesh Gajjala, Rajiv Raman +1
Wegner conjectured in 1965 that every finite family of axis-parallel rectangles satisfies , where is the minimum num…