19 citations · 37 across the 32 of their papers we have counts for
4 papers · 1 filter
Positive Planar Satisfiability Problems under 3-Connectivity Constraints
Md. Manzurul Hasan, Debajyoti Mondal, Md. Saidur Rahman
A 3-SAT problem is called positive and planar if all the literals are positive and the clause-variable incidence graph (i.e., SAT graph) is planar. The NAE 3-SAT and 1-in-3-SAT are…
APX-Hardness and Approximation for the k-Burning Number Problem
Debajyoti Mondal, N. Parthiban, V. Kavitha +1
Consider an information diffusion process on a graph that starts with burnt vertices, and at each subsequent step, burns the neighbors of the currently burnt vertices, as…
Token Swapping on Trees
Ahmad Biniaz, Kshitij Jain, Anna Lubiw +6
The input to the token swapping problem is a graph with vertices , and tokens with labels , one on each vertex. The goal is to get token…
The Complexity of Drawing a Graph in a Polygonal Region
Anna Lubiw, Tillmann Miltzow, Debajyoti Mondal
We prove that the following problem is complete for the existential theory of the reals: Given a planar graph and a polygonal region, with some vertices of the graph assigned to po…