Source author record

N. Parthiban

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

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics

Catalog footprint

Research overview

2works

3topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Oriented Diameter of Planar Triangulations

The diameter of an undirected or a directed graph is defined to be the maximum shortest path distance over all pairs of vertices in the graph. Given an undirected graph $G$ , we examine the problem of assigning directions to each edge of $G$ such that the diameter of the resulting oriented graph is minimized. The minimum diameter over all strongly connected orientations is called the oriented diameter of $G$ . The problem of determining the oriented diameter of a graph is known to be NP-hard, but the time-complexity question is open for planar graphs. In this paper we compute the exact value of the oriented diameter for triangular grid graphs. We then prove an $n/3$ lower bound and an $n/2+O(\sqrt{n})$ upper bound on the oriented diameter of planar triangulations. It is known that given a planar graph $G$ with bounded treewidth and a fixed positive integer $k$ , one can determine in linear time whether the oriented diameter of $G$ is at most $k$ . In contrast, we consider a weighted version of the oriented diameter problem and show it to be is weakly NP-complete for planar graphs with bounded pathwidth.

preprint2021arXiv

APX-Hardness and Approximation for the k-Burning Number Problem

Consider an information diffusion process on a graph $G$ that starts with $k>0$ burnt vertices, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as $k$ other unburnt vertices. The \emph{ $k$ -burning number} of $G$ is the minimum number of steps $b_k(G)$ such that all the vertices can be burned within $b_k(G)$ steps. Note that the last step may have smaller than $k$ unburnt vertices available, where all of them are burned. The $1$ -burning number coincides with the well-known burning number problem, which was proposed to model the spread of social contagion. The generalization to $k$ -burning number allows us to examine different worst-case contagion scenarios by varying the spread factor $k$ . In this paper we prove that computing $k$ -burning number is APX-hard, for any fixed constant $k$ . We then give an $O((n+m)\log n)$ -time 3-approximation algorithm for computing $k$ -burning number, for any $k\ge 1$ , where $n$ and $m$ are the number of vertices and edges, respectively. Finally, we show that even if the burning sources are given as an input, computing a burning sequence itself is an NP-hard problem.

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.