21 citations · 36 across the 14 of their papers we have counts for
18 papers
Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
Akash Kumar, Abhiruk Lahiri, C. Seshadhri
Consider a bounded-degree graph that belongs to a minor-closed family (such as planar graphs). Such a graph has a hyperfinite decomposition, wherein, for a sufficiently small $…
On Small Pair Decompositions for Point Sets
Kevin Buchin, Jacobus Conradi, Sariel Har-Peled +5
$\newcommand{\Re}{\mathbb{R}}$We study the minWSPD problem of computing the minimum-size well-separated pairs decomposition of a set of points, and show constant approximation algo…
Eliminating Majority Illusions
Foivos Fioravantes, Abhiruk Lahiri, Antonio Lauerbach +3
An opinion illusion refers to a phenomenon in social networks where agents may witness distributions of opinions among their neighbours that do not accurately reflect the true dist…
Parameterized Shortest Path Reconfiguration
Nicolas Bousquet, Kshitij Gajjar, Abhiruk Lahiri +1
An st-shortest path, or st-path for short, in a graph G is a shortest (induced) path from s to t in G. Two st-paths are said to be adjacent if they differ on exactly one vertex. A…
Approximating Fair -Min-Sum-Radii in Euclidean Space
Lukas Drexler, Annika Hennes, Abhiruk Lahiri +2
The -center problem is a classical clustering problem in which one is asked to find a partitioning of a point set into clusters such that the maximum radius of any clust…
Maximum edge colouring problem on graphs that exclude a fixed minor
Zdeněk Dvořák, Abhiruk Lahiri
The maximum edge colouring problem considers the maximum colour assignment to edges of a graph under the condition that every vertex has at most a fixed number of distinct coloured…
On -chromatic numbers of graphs having bounded sparsity parameters
Sandip Das, Abhiruk Lahiri, Soumen Nandi +2
An -graph is characterised by having types of arcs and types of edges. A homomorphism of an -graph to an -graph , is a vertex mapping that prese…
Square roots of nearly planar graphs
Zdeněk Dvořák, Benjamin Moore, Abhiruk Lahiri
We prove that it is NP-hard to decide whether a graph is the square of a 6-apex graph. This shows that the square root problem is not tractable for squares of sparse graphs (or eve…
On Comparable Box Dimension
Zdenek Dvorák, Daniel Goncalves, Abhiruk Lahiri +2
Two boxes in are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph is the minimum integer such…
Reconfiguring Shortest Paths in Graphs
Kshitij Gajjar, Agastya Vibhuti Jha, Manish Kumar +1
Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time so that all the intermediate paths are also shortest pat…
Parameterized Convexity Testing
Abhiruk Lahiri, Ilan Newman, Nithin Varma
In this work, we develop new insights into the fundamental problem of convexity testing of real-valued functions over the domain . Specifically, we present a nonadaptive algor…
Rainbow trees in uniformly edge-coloured graphs
Elad Aigner-Horev, Dan Hefetz, Abhiruk Lahiri
We obtain sufficient conditions for the emergence of spanning and almost-spanning bounded-degree {\sl rainbow} trees in various host graphs, having their edges coloured independent…
Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs
Zdeněk Dvořák, Abhiruk Lahiri
We give polynomial-time approximation schemes for monotone maximization problems expressible in terms of distances (up to a fixed upper bound) and efficiently solvable in graphs of…
Approximating MIS over equilateral -VPG graphs
Abhiruk Lahiri, Joydeep Mukherjee, C. R. Subramanian
We present an approximation algorithm for the maximum independent set (MIS) problem over the class of equilateral -VPG graphs. These are intersection graphs of -shaped plan…
Improved Approximation for Maximum Edge Colouring Problem
L Sunil Chandran, Abhiruk Lahiri, Nitin Singh
The anti-Ramsey number, is the minimum integer such that in any edge colouring of with colours there is a rainbow subgraph isomorphic to , i.e., a copy of…
Circular Separation Dimension of a Subclass of Planar Graphs
Arpitha P. Bharathi, Minati De, Abhiruk Lahiri
A pair of non-adjacent edges is said to be separated in a circular ordering of vertices, if the endpoints of the two edges do not alternate in the ordering. The circular separation…
Enumerations of vertices among all rooted ordered trees with levels and degrees
Sen-Peng Eu, Seunghyun Seo, Heesung Shin
In this paper we enumerate and give bijections for the following four sets of vertices among rooted ordered trees of a fixed size: (i) first-children of degree at level ,…
VPG and EPG bend-numbers of Halin Graphs
Mathew C. Francis, Abhiruk Lahiri
A piecewise linear curve in the plane made up of line segments, each of which is either horizontal or vertical, with consecutive segments being of different orientation is ca…