Browsing Department of Informatics by Author "Agrawal, Akanksha"
Now showing items 18 of 8

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 vertexlabeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection ... 
Graph modification problems: Beyond the known boundaries
Agrawal, Akanksha (Doctoral thesis, 20171117) 
Parameterized complexity classification of deletion to list matrixpartition for loworder 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 Mpartition of G with respect to L is a partition of V(G) into l parts, ... 
Parameterized complexity of conflictfree matchings and paths
Agrawal, Akanksha; Jain, Pallavi; Kanesh, Lawqueen; Saurabh, Saket (Journal article; Peer reviewed, 2019)An input to a conflictfree variant of a classical problem Gamma, called ConflictFree Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to ConflictFree Gamma in (I,H) ... 
The Parameterized Complexity of Guarding Almost Convex Polygons
Agrawal, Akanksha; Knudsen, Kristine Vitting Klinkby; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)The Art Gallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide ... 
Parameterized streaming algorithms for minones dSAT
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 MinOnes dSAT problem in the parameterized streaming model. An instance of the problem consists of a dCNF formula F and an integer k, and the objective is to determine if F has ... 
Path contraction faster than $2^n$
Agrawal, Akanksha; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Tale, Prafullkumar (Journal article; Peer reviewed, 2020)A graph $G$ is contractible to a graph $H$ if there is a set $X \subseteq E(G)$, such that $G/X$ is isomorphic to $H$. Here, $G/X$ is the graph obtained from $G$ by contracting all the edges in $X$. For a family of graphs ... 
Path Contraction Faster Than 2n
Agrawal, Akanksha; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Tale, Prafullkumar (Peer reviewed; Journal article, 2019)A graph G is contractible to a graph H if there is a set X subseteq E(G), such that G/X is isomorphic to H. Here, G/X is the graph obtained from G by contracting all the edges in X. For a family of graphs F, the FContraction ...