Zobrazeno 1 - 10
of 294
pro vyhledávání: '"Izumi, Taisuke"'
The independent set reconfiguration problem (ISReconf) is the problem of determining, for given independent sets I_s and I_t of a graph G, whether I_s can be transformed into I_t by repeatedly applying a prescribed reconfiguration rule that transform
Externí odkaz:
http://arxiv.org/abs/2407.11768
An \emph{$\alpha$-approximate vertex fault-tolerant distance sensitivity oracle} (\emph{$\alpha$-VSDO}) for a weighted input graph $G=(V, E, w)$ and a source vertex $s \in V$ is the data structure answering an $\alpha$-approximate distance from $s$ t
Externí odkaz:
http://arxiv.org/abs/2401.01103
In this paper, we propose a randomized $\tilde{O}(\mu(G))$-round algorithm for the maximum cardinality matching problem in the CONGEST model, where $\mu(G)$ means the maximum size of a matching of the input graph $G$. The proposed algorithm substanti
Externí odkaz:
http://arxiv.org/abs/2311.04140
We investigated the computational power of a single mobile agent in an $n$-node graph with storage (i.e., node memory). Generally, a system with one-bit agent memory and $O(1)$-bit storage is as powerful as that with $O(n)$-bit agent memory and $O(1)
Externí odkaz:
http://arxiv.org/abs/2211.00332
We investigate the computational power of the deterministic single-agent model where the agent and each node are equipped with a limited amount of persistent memory. Tasks are formalized as decision problems on properties of input graphs, i.e., the t
Externí odkaz:
http://arxiv.org/abs/2209.01906
The \emph{$f$-fault-tolerant connectivity labeling} ($f$-FTC labeling) is a scheme of assigning each vertex and edge with a small-size label such that one can determine the connectivity of two vertices $s$ and $t$ under the presence of at most $f$ fa
Externí odkaz:
http://arxiv.org/abs/2208.11459
We consider global problems, i.e. problems that take at least diameter time, even when the bandwidth is not restricted. We show that all problems considered admit efficient solutions in low-treewidth graphs. By ``efficient'' we mean that the running
Externí odkaz:
http://arxiv.org/abs/2205.14897
The first generic self-stabilizing transformer for local problems in a constrained bandwidth model is introduced. This transformer can be applied to a wide class of locally checkable labeling (LCL) problems, converting a given fault free synchronous
Externí odkaz:
http://arxiv.org/abs/2105.09756
In the rendezvous problem, two computing entities (called \emph{agents}) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the synchronous \emph{neighborhood rendezvous problem}, where the agents are
Externí odkaz:
http://arxiv.org/abs/2105.03638