Zobrazeno 1 - 10
of 715
pro vyhledávání: '"KRATOCHVÍL, Jan"'
Autor:
Jedličková, Nikola, Kratochvíl, Jan
A Hamiltonian path (cycle) in a graph is a path (cycle, respectively) which passes through all of its vertices. The problems of deciding the existence of a Hamiltonian cycle (path) in an input graph are well known to be NP-complete, and restricted cl
Externí odkaz:
http://arxiv.org/abs/2403.03668
We study a model of machine teaching where the teacher mapping is constructed from a size function on both concepts and examples. The main question in machine teaching is the minimum number of examples needed for any concept, the so-called teaching d
Externí odkaz:
http://arxiv.org/abs/2402.04907
Autor:
Jedličková, Nikola, Kratochvíl, Jan
A Hamiltonian path (a Hamiltonian cycle) in a graph is a path (a cycle, respectively) that traverses all of its vertices. The problems of deciding their existence in an input graph are well-known to be NP-complete, in fact, they belong to the first p
Externí odkaz:
http://arxiv.org/abs/2309.09228
Autor:
Cornelsen, Sabine, Da Lozzo, Giordano, Grilli, Luca, Gupta, Siddharth, Kratochvíl, Jan, Wolff, Alexander
Given a straight-line drawing of a graph, a segment is a maximal set of edges that form a line segment. Given a planar graph $G$, the segment number of $G$ is the minimum number of segments that can be achieved by any planar straight-line drawing of
Externí odkaz:
http://arxiv.org/abs/2308.15416
We study the following problem: Given a set $S$ of $n$ points in the plane, how many edge-disjoint plane straight-line spanning paths of $S$ can one draw? A well known result is that when the $n$ points are in convex position, $\lfloor n/2\rfloor$ su
Externí odkaz:
http://arxiv.org/abs/2306.07237