Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
Broadcasting under Structural Restrictions
Yudai Egami, Tatsuya Gima, Tesshu Hanaka +7
In the Telephone Broadcast problem we are given a graph with a designated source vertex . Our goal is to transmit a message, which is initially known only to ,…
cs.DS2024
Parameterized Spanning Tree Congestion
Michael Lampis, Valia Mitsou, Edouard Nemery +3
In this paper we study the Spanning Tree Congestion problem, where we are given a graph and are asked to find a spanning tree of minimum maximum congestion. Here, the…
cs.DS2024
Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
Syamantak Das, Nikhil Kumar, Daniel Vaz
Flow sparsification is a classic graph compression technique which, given a capacitated graph on terminals, aims to construct another capacitated graph , called a flow s…