Veena Prabhakaran

dblp:232/1686 · DBLP profile ↗
← Back
5ranked-venue papers
0as first author
4since 2021 · last 2025
0009-0005-4742-4358ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 5 · 4 since 2021
YearPublicationVenuePosition
2025 Token Sliding Independent Set Reconfiguration on Block Graphs
abstract
Let S be an independent set of a simple undirected graph G. Suppose that each vertex of S has a token placed on it. The tokens are allowed to be moved, one at a time, by sliding along the edges of G while maintaining the property that after each move, the vertices having tokens always form an independent set of G. We would like to determine whether the tokens can be eventually brought to stay on the vertices of another independent set S' of G in this manner. In other words, we would like to decide if we can transform S into S' through a sequence of steps, each of which involves substituting a vertex in the current independent set with one of its neighbours to obtain another independent set. This problem of determining if one independent set of a graph "is reachable" from another independent set of it is known to be PSPACE-hard even for split graphs, planar graphs, and graphs of bounded treewidth. Polynomial time algorithms have been obtained for certain graph classes like trees, interval graphs, claw-free graphs, and bipartite permutation graphs. We present a polynomial time algorithm for the problem on block graphs, which are the graphs in which every maximal 2-connected subgraph is a clique. Our algorithm is the first generalization of the known polynomial time algorithm for trees to a larger class of graphs.
Mathew C. Francis, Veena Prabhakaran
FSTTCS2
2025 Computing eternal vertex cover number of maximal outerplanar graphs in linear time
Jasine Babu, K. Murali Krishnan 0001, Veena Prabhakaran, Nandini J. Warrier
Theor. Comput. Sci.3
2022 On graphs whose eternal vertex cover number and vertex cover number coincide
Jasine Babu, L. Sunil Chandran, Mathew C. Francis, Veena Prabhakaran, Deepak Rajendraprasad, Nandini J. Warrier
Discret. Appl. Math.4
2021 A substructure based lower bound for eternal vertex cover number
Jasine Babu, Veena Prabhakaran, Arko Sharma
Theor. Comput. Sci.2
2020 A New Lower Bound for the Eternal Vertex Cover Number of Graphs
Jasine Babu, Veena Prabhakaran
COCOON2