BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Indra Rajasingh

Indra Rajasingh contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsComputational ComplexityDiscrete Mathematics

Trust snapshot

Quick read

Trust 13 - UnverifiedVerification L1Unclaimed author
2works
0followers
3topics
3close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

2 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access