Schürenberg, Torben

Lade...
Vorschaubild
Preferred name
Schürenberg, Torben
Official Name
Schürenberg, Torben
Alternative Name
Schürenberg, T.
Main Affiliation
ORCID

Einstellungen

Gerade angezeigt 1 - 1 von 1
  • Lade...
    Vorschaubild
    Some of the metrics are blocked by your 
    consent settings
    Item-typ:Veröffentlichung,
    On the complexity of Min-Max Star Partitioning and firefighting, and the impact of selfish behavior in packet routing
    (2026-04-29)
    Schürenberg, Torben
    ;
    Schmand, Daniel
    ;
    Weltge, Stefan
    ;
    Schmand, Daniel
    This dissertation investigates three central problems in the realm of graph theory, combinatorial optimization, and algorithmic game theory. The focus lies on computational complexity, efficient algorithms, and the impact of selfish behavior in networks. Star Partitioning: We introduce a novel Star Partitioning problem, where the edges of a graph are partitioned into stars to minimize the maximum number of stars a node participates in, while respecting node-specific capacities. Firefighting on Graphs: We investigate a pursuit–evasion game, where a fire spreads across the nodes of a graph, and a limited number of firefighters try to extinguish it. Selfish Behavior in Packet Routing: We analyze a packet routing game with discrete time steps, where players select source-to-destination paths in networks with limited edge capacities. The social objective is to minimize the completion time, that is, the time it takes for the last player to reach the destination.
    Dissertation
      34  35