1 citations · 1 across the 10 of their papers we have counts for
11 papers
Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection
Krishnendu Chatterjee, Jan Matyáš Křišťan, Stefan Schmid +2
Payment channel networks (PCNs) are a promising technology that alleviates blockchain scalability by shifting the transaction load from the blockchain to the PCN. Nevertheless, the…
Solving Multiagent Path Finding on Highly Centralized Networks
Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan +3
The Mutliagent Path Finding (MAPF) problem consists of identifying the trajectories that a set of agents should follow inside a given network in order to reach their desired destin…
Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures
Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan +2
Consider the scenario where multiple agents have to move in an optimal way through a network, each one towards their ending position while avoiding collisions. By optimal, we mean…
Reconfiguration Using Generalized Token Jumping
Jan Matyáš Křišťan, Jakub Svoboda
In reconfiguration, we are given two solutions to a graph problem, such as Vertex Cover or Dominating Set, with each solu tion represented by a placement of tokens on vertices of t…
Decreasing verification radius in local certification
Laurent Feuilloley, Jan Janoušek, Jan Matyáš Křišťan +1
This paper deals with local certification, specifically locally checkable proofs: given a graph property, the task is to certify whether a graph satisfies the property. The verific…
Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology
Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan +2
In the Multiagent Path Finding problem (MAPF for short), we focus on efficiently finding non-colliding paths for a set of agents on a given graph , where each agent seeks a…
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…
Efficient attack sequences in m-eternal domination
Václav Blažej, Jan Matyáš Křišťan, Tomáš Valla
We study the m-eternal domination problem from the perspective of the attacker. For many graph classes, the minimum required number of guards to defend eternally is known. By defin…
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…