Source author record

Veena Prabhakaran

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics Data Structures and Algorithms math.CO

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Eternal vertex cover number of maximal outerplanar graphs

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 for bipartite graphs is open. There is a quadratic complexity algorithm known for this problem for chordal graphs. Maximal outerplanar graphs forms a subclass of chordal graphs, for which no algorithm of sub-quadratic time complexity is known. In this paper, we obtain a recursive algorithm of linear time for computing eternal vertex cover number of maximal outerplanar graphs.

preprint2020arXiv

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

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 time recursive algorithm for computing the eternal vertex cover number of cactus graphs. Unlike other graph classes for which polynomial time algorithms for eternal vertex cover number are based on efficient computability of a known lower bound directly derived from minimum vertex cover, we show that it is a certain substructure property that helps the efficient computation of eternal vertex cover number of cactus graphs. An extension of the result to graphs in which each block is an edge, a cycle or a biconnected chordal graph is also presented.

preprint2020arXiv

A new lower bound for eternal vertex cover number

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 time algorithm for computing the eternal vertex cover number of chordal graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.