Výsledky vyhledávání - "Prabhakaran, Veena"

Report

Token sliding independent set reconfiguration on block graphs

Autor: Francis, Mathew C., Prabhakaran, Veena

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$, so that after each move, the vertices havi

Externí odkaz: http://arxiv.org/abs/2410.07060

Zobrazit plný text záznamu

Report

Eternal vertex cover number of maximal outerplanar graphs

Autor: Babu, Jasine, Krishnan, K. Murali, Prabhakaran, Veena, Warrier, Nandini J.

Eternal vertex cover problem is a variant of the classical vertex cover problem modeled as a two player attacker-defender game. Computing eternal vertex cover number of graphs is known to be NP-hard in general and the complexity status of the problem

Externí odkaz: http://arxiv.org/abs/2201.06577

Zobrazit plný text záznamu

Report

A Linear Time Algorithm for Computing the Eternal Vertex Cover Number of Cactus Graphs

Autor: Babu, Jasine, Prabhakaran, Veena, Sharma, Arko

The eternal vertex cover problem is a dynamic variant of the classical vertex cover problem. It is NP-hard to compute the eternal vertex cover number of graphs and known algorithmic results for the problem are very few. This paper presents a linear t

Externí odkaz: http://arxiv.org/abs/2005.08058

Zobrazit plný text záznamu

Report

A new lower bound for eternal vertex cover number

Autor: Babu, Jasine, Prabhakaran, Veena

We obtain a new lower bound for the eternal vertex cover number of an arbitrary graph $G$, in terms of the cardinality of a vertex cover of minimum size in $G$ containing all its cut vertices. The consequences of the lower bound includes a quadratic

Externí odkaz: http://arxiv.org/abs/1910.05042

Zobrazit plný text záznamu

Report

On Graphs whose Eternal Vertex Cover Number and Vertex Cover Number Coincide

Autor: Babu, Jasine, Chandran, L. Sunil, Francis, Mathew, Prabhakaran, Veena, Rajendraprasad, Deepak, Warrier, J. Nandini

The eternal vertex cover problem is a variant of the classical vertex cover problem where a set of guards on the vertices have to be dynamically reconfigured from one vertex cover to another in every round of an attacker-defender game. The minimum nu

Externí odkaz: http://arxiv.org/abs/1812.05125

Zobrazit plný text záznamu