Anil Maheshwari

activity

20242026

collaborators

10 papers

cs.DS2026

Minimum Sum Vertex Cover via Minimum Vertex Cover

Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +2

The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered.…

cs.DM2026

Completely Independent Steiner Trees

Anil Maheshwari, Karthik Murali, Michiel Smid

Spanning trees are fundamental for efficient communication in networks. For fault-tolerant communication, it is desirable to have multiple spanning trees to ensure resilience again…

cs.CG2026

Linear-Time $(1 + ε)$ -Approximation Algorithms for Two-Line-Center Problems

Chaeyoon Chung, Anil Maheshwari, Michiel Smid

Given a set $S$ of $n$ points in the plane, we study the two-line-center problem: finding two lines that minimize the maximum distance from each point in $S$ to its closest line. W…

cs.CG2025

Polychromatic Coloring of Tuples in Hypergraphs

Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +3

A hypergraph $H$ consists of a set $V$ of vertices and a set $E$ of hyperedges that are subsets of $V$ . A $t$ -tuple of $H$ is a subset of $t$ vertices of $V$ . A $t$ -tuple $k$ -color…

cs.CG2025

Closest Pair Queries in Vertical Slabs and Tight Bounds on the Number of Possible Answers

Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung +6

Let $S$ be a set of $n$ points in $R^{d}$ , where $d \geq 2$ is a constant, and let $H_{1}, H_{2}, \dots, H_{m + 1}$ be a sequence of vertical hyperplanes that are sorted by their fi…

cs.CG2024

Computing Oriented Spanners and their Dilation

Kevin Buchin, Antonia Kalb, Anil Maheshwari +4

Given a point set $P$ in a metric space and a real number $t \geq 1$ , an \emph{oriented $t$ -spanner} is an oriented graph $G = (P, E)$ , where for eve…

cs.CG2024

Contiguous Boundary Guarding

Ahmad Biniaz, Anil Maheshwari, Joseph S. B. Mitchell +3

We study the problem of guarding the boundary of a simple polygon with a minimum number of guards such that each guard covers a contiguous portion of the boundary. First, we presen…

cs.CG2024

Euclidean Maximum Matchings in the Plane---Local to Global

Ahmad Biniaz, Anil Maheshwari, Michiel Smid

Let $M$ be a perfect matching on a set of points in the plane where every edge is a line segment between two points. We say that $M$ is globally maximum if it is a maximum-length m…

cs.CG2024

Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults

Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +1

Let $H$ be an edge-weighted graph, and let $G$ be a subgraph of $H$ . We say that $G$ is an $f$ -fault-tolerant $t$ -spanner for $H$ , if the following is true for any subset $F$ of at…

cs.CG2024

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets

Aritra Banik, Sayani Das, Anil Maheshwari +6

In the Minimum Consistent Subset (MCS) problem, we are presented with a connected simple undirected graph $G = (V, E)$ , consisting of a vertex set $V$ of size $n$ and an edge set $E$ .…

Minimum Sum Vertex Cover via Minimum Vertex Cover

Completely Independent Steiner Trees

Linear-Time (1+ε)-Approximation Algorithms for Two-Line-Center Problems

Polychromatic Coloring of Tuples in Hypergraphs

Closest Pair Queries in Vertical Slabs and Tight Bounds on the Number of Possible Answers

Computing Oriented Spanners and their Dilation

Contiguous Boundary Guarding

Euclidean Maximum Matchings in the Plane---Local to Global

Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets

Linear-Time $(1 + ε)$ -Approximation Algorithms for Two-Line-Center Problems