Now showing items 1-8 of 8

• #### Connecting the Dots (with Minimum Crossings) ﻿

(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 ...
• #### Graph modification problems: Beyond the known boundaries ﻿

(Doctoral thesis, 2017-11-17)
• #### Parameterized complexity classification of deletion to list matrix-partition for low-order matrices ﻿

(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 ﻿

(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) ...
• #### The Parameterized Complexity of Guarding Almost Convex Polygons ﻿

(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 min-ones d-SAT ﻿

(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 ...
• #### Path contraction faster than $2^n$ ﻿

(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 ﻿

(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 F-Contraction ...