Zobrazeno 1 - 10
of 62
pro vyhledávání: '"Zylinski, Pawel"'
Autor:
Dereniowski, Dariusz, Dybizbański, Janusz, Karpiński, Przemysław, Zakrzewski, Michał, Żyliński, Paweł
We present a simple linear-time algorithm that finds a spanning tree $T$ of a given $2$-edge-connected graph $G$ such that each vertex $v$ of $T$ has degree at most $\lceil \frac{\deg_G(v)}{2}\rceil + 1$.
Externí odkaz:
http://arxiv.org/abs/2410.20137
Publikováno v:
Computing in Geometry and Topology, 3(2), 4:1-4:12 (2024)
Cops and Robber is a family of two-player games played on graphs in which one player controls a number of cops and the other player controls a robber. In alternating turns, each player moves (all) their figures. The cops try to capture the robber whi
Externí odkaz:
http://arxiv.org/abs/2301.05514
Let $r$ be a point in the first quadrant $Q_1$ of the plane $\mathbb{R}^2$ and let $P \subset Q_1$ be a set of points such that for any $p \in P$, its $x$- and $y$-coordinate is at least as that of $r$. A rectilinear Steiner arborescence for $P$ with
Externí odkaz:
http://arxiv.org/abs/2210.04576
We present an $O(nrG)$ time algorithm for computing and maintaining a minimum length shortest watchman tour that sees a simple polygon under monotone visibility in direction $\theta$, while $\theta$ varies in $[0,180^{\circ})$, obtaining the directio
Externí odkaz:
http://arxiv.org/abs/2007.08368
A graph $G$ is a $D\!D_2$-graph if it has a pair $(D,D_2)$ of disjoint sets of vertices of $G$ such that $D$ is a dominating set and $D_2$ is a 2-dominating set of $G$. We provide several characterizations and hardness results concerning $D\!D_2$-gra
Externí odkaz:
http://arxiv.org/abs/1903.06129
A dominating set of a graph $G$ is a set $D\subseteq V_G$ such that every vertex in $V_G-D$ is adjacent to at least one vertex in $D$, and the domination number $\gamma(G)$ of $G$ is the minimum cardinality of a dominating set of $G$. In this paper w
Externí odkaz:
http://arxiv.org/abs/1903.03052
Publikováno v:
Journal of Combinatorial Optimization (2020) 39:55-71
A dominating set of a graph $G$ is a set $D\subseteq V_G$ such that every vertex in $V_G-D$ is adjacent to at least one vertex in $D$, and the domination number $\gamma(G)$ of $G$ is the minimum cardinality of a dominating set of $G$. A set $C\subset
Externí odkaz:
http://arxiv.org/abs/1802.09051
Publikováno v:
Journal of Global Optimization (2021) 80, 887-920
Let $\mathcal{O}$ be a set of $k$ orientations in the plane, and let $P$ be a simple polygon in the plane. Given two points $p,q$ inside $P$, we say that $p$ $\mathcal{O}$-\emph{sees} $q$ if there is an $\mathcal{O}$-\emph{staircase} contained in $P$
Externí odkaz:
http://arxiv.org/abs/1802.05995
Autor:
Topp, Jerzy, Żyliński, Paweł
Let $\gamma(G)$ and $\beta(G)$ denote the domination number and the covering number of a graph $G$, respectively. A connected non-trivial graph $G$ is said to be $\gamma\beta$-{perfect} if $\gamma(H)=\beta(H)$ for every non-trivial induced connected
Externí odkaz:
http://arxiv.org/abs/1802.03392
Publikováno v:
Journal of Computer and System Sciences 102: 57-68 (2019)
We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset~$\mat
Externí odkaz:
http://arxiv.org/abs/1712.00316