13 citations · 48 across the 11 of their papers we have counts for
4 papers · 1 filter
Overlapping Communities in Social Networks
Jan Dreier, Philipp Kuinke, Rafael Przybylski +3
Complex networks can be typically broken down into groups or modules. Discovering this "community structure" is an important step in studying the large-scale structure of networks.…
Kernelization and Sparseness: the case of Dominating Set
Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin +9
We prove that for every positive integer and for every graph class of bounded expansion, the -Dominating Set problem admits a linear kernel on graphs from $\mat…
Structural Sparsity of Complex Networks: Bounded Expansion in Random Models and Real-World Graphs
Erik D. Demaine, Felix Reidl, Peter Rossmanith +3
This research establishes that many real-world networks exhibit bounded expansion, a strong notion of structural sparsity, and demonstrates that it can be leveraged to design effic…
A Faster Parameterized Algorithm for Treedepth
Felix Reidl, Peter Rossmanith, Fernando Sanchez Villaamil +1
The width measure \emph{treedepth}, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence o…