3 papers
cs.DM2026
Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
Hanno von Bergen, Larissa Fastenau, Enna Gerhard +8
We study solution discovery, where the goal is to obtain a feasible solution to a problem from an initial configuration by a bounded sequence of local moves. In many applications,…
cs.GT2025
Network Creation Games with 2-Neighborhood Maximization
Merlin de la Haye, Pascal Lenzner, Daniel Schmand +1
Network creation games are well-established for investigating the decentralized formation of communication networks, like the Internet or social networks. In these games, selfish a…
cs.GT2023
Solving Woeginger's Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games
Andrei Constantinescu, Pascal Lenzner, Rebecca Reiffenhäuser +2
A decade ago, Gerhard Woeginger posed an open problem that became well-known as "Woeginger's Hiking Problem": Consider a group of people that want to go hiking; everyone expres…