2 citations · 4 across the 18 of their papers we have counts for
7 papers · 1 filter
Robust Contraction Decomposition for Minor-Free Graphs and its Applications
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +6
We prove a robust contraction decomposition theorem for -minor-free graphs, which states that given an -minor-free graph and an integer , one can partition in polynomi…
Structural Parameterization of Locating-Dominating Set and Test Cover
Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar +1
We investigate structural parameterizations of two identification problems: LOCATING-DOMINATING SET and TEST COVER. In the first problem, an input is a graph on vertices an…
Metric Dimension and Geodetic Set Parameterized by Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya +4
For a graph , a subset is called a resolving set of if, for any two vertices , there exists a vertex such that . T…
Revisiting Path Contraction and Cycle Contraction
R. Krithika, V. K. Kutty Malu, Prafullkumar Tale
The Path Contraction and Cycle Contraction problems take as input an undirected graph with vertices, edges and an integer and determine whether one can obtain a pat…
Conflict and Fairness in Resource Allocation
Susobhan Bandopadhyay, Aritra Banik, Sushmita Gupta +4
In the standard model of fair allocation of resources to agents, every agent has some utility for every resource, and the goal is to assign resources to agents so that the agents'…
Double Exponential Lower Bound for Telephone Broadcast
Prafullkumar Tale
Consider the Telephone Broadcast problem in which an input is a connected graph on vertices, a source vertex , and a positive integer . The objective is to d…