62 citations · 316 across the 38 of their papers we have counts for
Showing 2013 · cs.DSShow all
3 papers · 2 filters
cs.DS2013★ 7 cited
The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree
Jakub Łącki, Jakub Oćwieja, Marcin Pilipczuk +2
In this paper we study the Steiner tree problem over a dynamic set of terminals. We consider the model where we are given an -vertex graph with positive real edge we…
cs.DS2013★ 1 cited
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski +1
We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is…
cs.DS2013★ 10 cited
Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors
Harold N. Gabow, Piotr Sankowski
Let G=(V,E) be a graph with f:V\to Z_+ a function assigning degree bounds to vertices. We present the first efficient algebraic algorithm to find an f-factor. The time is \tilde{O}…