3 papers
cs.DS2026
Parameterized Complexity of Connected Network Microaggregation: The Role of Cluster Size
Ajinkya Gaikwad, Dušan Knop, Tomáš Valla
Network microaggregation is a fundamental technique in statistical disclosure control, where vertices of a graph are partitioned into clusters satisfying size constraints and admit…
cs.CC2023
Treewidth is NP-Complete on Cubic Graphs (and related results)
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke +6
In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by B…
cs.DS2021
Balancing the Spread of Two Opinions in Sparse Social Networks
Dušan Knop, Šimon Schierreich, Ondřej Suchý
Inspired by the famous Target Set Selection problem, we propose a new discrete model to simultaneously spread two opinions within a social network and perform an initial study of i…