2 citations · 4 across the 11 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.DM2022
Recognizing Geometric Intersection Graphs Stabbed by a Line
Dibyayan Chakraborty, Kshitij Gajjar, Irena Rusu
In this paper, we determine the computational complexity of recognizing two graph classes, \emph{grounded L}-graphs and \emph{stabbable grid intersection} graphs. An L-shape is mad…
cs.CC2022
Monotone Classes Beyond VNP
Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse
In this work, we study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat 2008, Koiran and Perifel 2009, Malod 2011, Mahajan…