Showing 2022Show all
2 papers · 1 filter
cs.DS2022
An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set
Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan
We study the CONNECTED η-TREEDEPTH DELETION problem where the input instance is an undireted graph G = (V, E) and an integer k. The objective is to decide if G has a set S \subsete…
cs.DS2022
The Parameterized Complexity of Welfare Guarantees in Schelling Segregation
Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith
Schelling's model considers types of agents each of whom needs to select a vertex on an undirected graph, where every agent prefers to neighbor agents of the same type. We are…