Showing 2026Show all
2 papers · 1 filter
cs.DS2026
Sparsification Framework for Directed Densest Subgraph
Slobodan Mitrović, Theodore Pan
We develop a new approach for computing approximate directed densest subgraphs (DDS). Our main result is a sparsification procedure that reduces a directed graph on vertice…
cs.DS2026
Fixed-Threshold Peeling in Sublinear MPC: Round-Approximation Tradeoffs and Applications
Slobodan Mitrović, Theodore Pan, Wen-Horng Sheu
A number of fundamental graph problems admit simple algorithms based on iterative peeling: repeatedly remove all vertices whose current degree is below a fixed threshold. This para…