4 papers
Finding Minimum Distance Preservers: A Parameterized Study
Kirill Simonov, Farehe Soheil, Shaily Verma
For a given graph and a subset of vertices , a \emph{distance preserver} is a subgraph of that preserves shortest paths between the vertices of . We distinguish betwe…
Metric Hedonic Games on the Line
Merlin de la Haye, Pascal Lenzner, Farehe Soheil +1
Hedonic games are fundamental models for investigating the formation of coalitions among a set of strategic agents, where every agent has a certain utility for every possible coali…
Parameterized Complexity of Vehicle Routing
Michelle Döring, Jan Fehse, Tobias Friedrich +6
The Vehicle Routing Problem (VRP) is a popular generalization of the Traveling Salesperson Problem. Instead of one salesperson traversing the entire weighted, undirected graph ,…
Binary -Center with Missing Entries: Structure Leads to Tractability
Farehe Soheil, Kirill Simonov, Tobias Friedrich
$\kC$ clustering is a fundamental classification problem, where the task is to categorize the given collection of entities into clusters and come up with a representative for e…