19 citations · 118 across the 26 of their papers we have counts for
6 papers · 1 filter
Multi-Player Diffusion Games on Graph Classes
Laurent Bulteau, Vincent Froese, Nimrod Talmon
We study competitive diffusion games on graphs introduced by Alon et al. [1] to model the spread of influence in social networks. Extending results of Roshanbin [8] for two players…
The Complexity of Finding Effectors
Laurent Bulteau, Stefan Fafianie, Vincent Froese +2
The NP-hard EFFECTORS problem on directed graphs is motivated by applications in network mining, particularly concerning the analysis of probabilistic information-propagation proce…
Win-Win Kernelization for Degree Sequence Completion Problems
Vincent Froese, André Nichterlein, Rolf Niedermeier
We study provably effective and efficient data reduction for a class of NP-hard graph modification problems based on vertex degree properties. We show fixed-parameter tractability…
Triangle counting in dynamic graph streams
Laurent Bulteau, Vincent Froese, Konstantin Kutzkov +1
Estimating the number of triangles in graph streams using a limited amount of memory has become a popular topic in the last decade. Different variations of the problem have been st…
Network-Based Vertex Dissolution
René van Bevern, Robert Bredereck, Jiehua Chen +3
We introduce a graph-theoretic vertex dissolution model that applies to a number of redistribution scenarios such as gerrymandering in political districting or work balancing in an…
Partitioning Perfect Graphs into Stars
René van Bevern, Robert Bredereck, Laurent Bulteau +4
The partition of graphs into "nice" subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same-size st…