From the 1 of 3 linked papers with an AI index.
3 papers
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…
Identifying Codes Kernelization Limitations
Aritra Banik, Praneet Kumar Patra, Adele Anna Rescigno +1
The Identifying Code (IC) problem seeks a vertex subset whose intersection with every vertex's closed neighborhood is unique, enabling fault detection in multiprocessor systems and…
Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
Ajinkya Gaikwad, Hitendra Kumar, S. Padmapriya +3
We study a family of graph modification problems called the F-Vertex Splitting problem. Given a graph G, the task is to determine whether G can be transformed into a graph G-prime…