Source author record

Indra Rajasingh

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 Social and Information Networks

Catalog footprint

Research overview

3works

4topics

4close 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.

preprint2014arXiv

Towards Investigating Substructures and Role Recognition in Goal Oriented Online Communities

In this paper, we apply social network analytic methods to unveil the structural dynamics of a popular open source goal oriented IRC community, Ubuntu. The primary objective is to track the development of this ever growing community over time using a social network lens and examine the dynamically changing participation patterns of people. Specifically, our research seeks out to investigate answers to the following question: How can the communication dynamics help us in delineating important substructures in the IRC network? This gives an insight into how open source learning communities function internally and what drives the exhibited IRC behavior. By application of a consistent set of social network metrics, we discern factors that affect people's embeddedness in the overall IRC network, their structural influence and importance as discussion initiators or responders. Deciphering these informal connections are crucial for the development of novel strategies to improve communication and foster collaboration between people conversing in the IRC channel, there by stimulating knowledge flow in the network. Our approach reveals a novel network skeleton, that more closely resembles the behavior of participants interacting online. We highlight bottlenecks to effective knowledge dissemination in the IRC, so that focused attention could be provided to communities with peculiar behavioral patterns. Additionally, we explore interesting research directions in augmenting the study of communication dynamics in the IRC.

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.