3 citations · 6 across the 8 of their papers we have counts for
3 papers · 1 filter
The Complexity of Diameter on H-free graphs
Jelle J. Oostveen, Daniël Paulusma, Erik Jan van Leeuwen
The intensively studied Diameter problem is to find the diameter of a given connected graph. We investigate, for the first time in a structured manner, the complexity of Diameter f…
Parameterized Complexity of Streaming Diameter and Connectivity Problems
Jelle J. Oostveen, Erik Jan van Leeuwen
We initiate the investigation of the parameterized complexity of Diameter and Connectivity in the streaming paradigm. On the positive end, we show that knowing a vertex cover of si…
Streaming Deletion Problems Parameterized by Vertex Cover
Jelle J. Oostveen, Erik Jan van Leeuwen
Streaming is a model where an input graph is provided one edge at a time, instead of being able to inspect it at will. In this work, we take a parameterized approach by assuming a…