From the 1 of 10 linked papers with an AI index.
10 papers
Fair, Efficient and Connected Allocations on Graphs
Susobhan Bandopadhyay, Anish Datta, Palash Dey +2
We study the classical and parameterized complexity of efficient connected allocation problems on graphs, where efficiency is measured by egalitarian and utilitarian welfare maximi…
Exploiting Graph Structure for Near-Optimal Broadcasting
Rudranarayan Kar, Praneet Kumar Patra, Diya Roy +1
The paper studies faster approximation algorithms for the graph broadcasting problem, providing additive‑approximation schemes and improved exact algorithms while also showing para…
A Deterministic Separation Lemma
Abhishek Sahu
The \emph{Separation Lemma} is a simple yet powerful tool, akin to the well-known \emph{Isolation Lemma}, that guarantees the uniqueness of certain set sums. Bandopadhyay et al.\ i…
On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints
Susobhan Bandopadhyay, Aritra Banik, Diptapriyo Majumdar +1
Given an undirected graph G and a set A \subseteq V(G), an A-path is a path in G that starts and ends at two distinct vertices of A with intermediate vertices in V(G) \setminus A.…
Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
Aritra Banik, Sujoy Bhore, Palash Dey +1
The kidney exchange mechanism allows many patient-donor pairs who are otherwise incompatible with each other to come together and exchange kidneys along a cycle. However, due to in…
Learning with Structure: Computing Consistent Subsets on Structurally-Regular Graphs
Aritra Banik, Mano Prakash Parthasarathi, Venkatesh Raman +2
The Minimum Consistent Subset (MCS) problem arises naturally in the context of supervised clustering and instance selection. In supervised clustering, one aims to infer a meaningfu…