3 papers
cs.DS2026
Exploiting Graph Structure for Near-Optimal Broadcasting
Rudranarayan Kar, Praneet Kumar Patra, Diya Roy +1
Telephone broadcasting is a classical model for spreading information in a network. Given a connected graph with source vertex , each informed vertex may inform exactly…
cs.CC2025
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…
cs.DS2025
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…