Zobrazeno 1 - 10
of 32
pro vyhledávání: '"Jan Matyáš"'
Autor:
Křišťan, Jan Matyáš, Svoboda, Jakub
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 the graph. Our task is to reconfigure one into the other using small st
Externí odkaz:
http://arxiv.org/abs/2411.12582
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 verification of this certification needs to be done locally without the knowl
Externí odkaz:
http://arxiv.org/abs/2408.10757
Autor:
Samuel Španihel, Jan Matyáš, Jan Štětina, Kamila Valoušková, Zdeněk Havlíček, Lucie Langová, Ivana Novotná
Publikováno v:
Archaeologia Historica, Vol 44, Iss 1 (2019)
Trinitářský klášter v Zašové je jedním z mála klášterů tohoto řádu na území České republiky. Během své krátké existence (1725–1783) řádoví bratři nejenže působili jako obnovitelé katolické víry na převážně evangel
Externí odkaz:
https://doaj.org/article/91de2eb8522342a3a20b96b6665f11e6
In the Multiagent Path Finding problem (MAPF for short), we focus on efficiently finding non-colliding paths for a set of $k$ agents on a given graph $G$, where each agent seeks a path from its source vertex to a target. An important measure of the q
Externí odkaz:
http://arxiv.org/abs/2312.09646
Autor:
Křišťan, Jan Matyáš, Svoboda, Jakub
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 Token Sliding model. In this problem, a graph is provided along with its
Externí odkaz:
http://arxiv.org/abs/2307.10847
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 defender can move each guard to a neighboring vertex and must move a g
Externí odkaz:
http://arxiv.org/abs/2301.05155
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 definition, if the defender has less than the required number of guards, th
Externí odkaz:
http://arxiv.org/abs/2204.02720
Autor:
Blažej, Václav, Choudhary, Pratibha, Knop, Dušan, Křišťan, Jan Matyáš, Suchý, Ondřej, Valla, Tomáš
Given an undirected graph $G=(V,E)$, vertices $s,t\in V$, and an integer $k$, Tracking Shortest Paths requires deciding whether there exists a set of $k$ vertices $T\subseteq V$ such that for any two distinct shortest paths between $s$ and $t$, say $
Externí odkaz:
http://arxiv.org/abs/2202.11927
Autor:
Blažej, Václav, Choudhary, Pratibha, Knop, Dušan, Křišťan, Jan Matyáš, Suchý, Ondřej, Valla, Tomáš
Consider a vertex-weighted graph $G$ with a source $s$ and a target $t$. Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from $s$ to $t$ is unique. In this work, we derive a
Externí odkaz:
http://arxiv.org/abs/2108.01430
Given a graph $G$, guards are placed on vertices of $G$. Then vertices are subject to an infinite sequence of attacks so that each attack must be defended by a guard moving from a neighboring vertex. The m-eternal domination number is the minimum num
Externí odkaz:
http://arxiv.org/abs/1907.07910