Browsing Registrations from Cristin by Author "Agrawal, Akanksha"

Now showing items 1-4 of 4

    • Connecting the Dots (with Minimum Crossings) 

      Agrawal, Akanksha; Guspiel, Grzegorz; Madathil, Jayakrishnan; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2019)
      We study a prototype Crossing Minimization problem, defined as follows. Let F be an infinite family of (possibly vertex-labeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection ...

    • Parameterized complexity classification of deletion to list matrix-partition for low-order matrices 

      Agrawal, Akanksha; Kolay, Sudeshna; Madathil, Jayakrishnan; Saurabh, Saket (Journal article; Peer reviewed, 2019)
      Given a symmetric l x l matrix M=(m_{i,j}) with entries in {0,1,*}, a graph G and a function L : V(G) - > 2^{[l]} (where [l] = {1,2,...,l}), a list M-partition of G with respect to L is a partition of V(G) into l parts, ...

    • Parameterized complexity of conflict-free matchings and paths 

      Agrawal, Akanksha; Jain, Pallavi; Kanesh, Lawqueen; Saurabh, Saket (Journal article; Peer reviewed, 2019)
      An input to a conflict-free variant of a classical problem Gamma, called Conflict-Free Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to Conflict-Free Gamma in (I,H) ...

    • Parameterized streaming algorithms for min-ones d-SAT 

      Agrawal, Akanksha; Bonnet, Édouard; Curticapean, Radu; Miltzow, Tillmann; Saurabh, Saket; Biswas, Arindam; Brettell, Nick; Marx, Dániel; Raman, Venkatesh (Journal article; Peer reviewed, 2019)
      In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has ...