12 citations · 23 across the 13 of their papers we have counts for
10 papers · 1 filter
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…
Parameterized Complexity of Edge-Constrained Graph Partitioning
Ajinkya Gaikwad, Jan Pokorný, Tomáš Valla
We study the Edge-Constrained Graph Partitioning Problem (ECGP), which asks whether the vertices of a graph can be partitioned into r parts, each inducing at least gamma edges. We…
Computing m-Eternal Domination Number of Cactus Graphs in Linear Time
Václav Blažej, Jan Matyáš Křišťan, Tomáš Valla
In m-eternal domination attacker and defender play on a graph. Initially, the defender places guards on vertices. In each round, the attacker chooses a vertex to attack. Then, the…
On Polynomial Kernels for Traveling Salesperson Problem and its Generalizations
Václav Blažej, Pratibha Choudhary, Dušan Knop +3
For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important a…
Polynomial Kernels for Tracking Shortest Paths
Václav Blažej, Pratibha Choudhary, Dušan Knop +3
Given an undirected graph , vertices , and an integer , Tracking Shortest Paths requires deciding whether there exists a set of vertices su…
Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set
Václav Blažej, Pratibha Choudhary, Dušan Knop +3
Consider a vertex-weighted graph with a source and a target . Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of track…