1 citations · 1 across the 10 of their papers we have counts for
4 papers · 1 filter
Shortest Dominating Set Reconfiguration under Token Sliding
Jan Matyáš Křišťan, Jakub Svoboda
In this paper, we present novel algorithms that efficiently compute a shortest reconfiguration sequence between two given dominating sets in trees and interval graphs under the Tok…
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…
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…