Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Designing Capacitated Subnetworks for Shortest Path Routing
Markus Chimani, Max Ilsen
In pursuit of higher energy efficiency in computer networks, one subfield of green traffic engineering aims at reducing the size of a network during times of low traffic, while sti…
cs.DS2025
Simple Approximations for General Spanner Problems
Fritz Bökler, Markus Chimani, Henning Jasper
Consider a graph with n nodes and m edges, independent edge weights and lengths, and arbitrary distance demands for node pairs. The spanner problem asks for a minimum-weight subgra…
cs.DS2024
Exact Minimum Weight Spanners via Column Generation
Fritz Bökler, Markus Chimani, Henning Jasper +1
Given a weighted graph , a minimum weight -spanner is a least-weight subgraph that preserves minimum distances between all node pairs up to a factor of .…