Zobrazeno 1 - 10
of 1 261
pro vyhledávání: '"Okamoto, Yoshio"'
This paper collects all descriptions of solvers and ISR instances submitted to CoRe Challenge 2023.
Comment: arXiv admin note: text overlap with arXiv:2208.02495, arXiv:2207.13959
Comment: arXiv admin note: text overlap with arXiv:2208.02495, arXiv:2207.13959
Externí odkaz:
http://arxiv.org/abs/2310.17136
Autor:
Gomes, Guilherme C. M., Legrand-Duchesne, Clément, Mahmoud, Reem, Mouawad, Amer E., Okamoto, Yoshio, Santos, Vinicius F. dos, van der Zanden, Tom C.
We study the problem of reconfiguring one minimum $s$-$t$-separator $A$ into another minimum $s$-$t$-separator $B$ in some $n$-vertex graph $G$ containing two non-adjacent vertices $s$ and $t$. We consider several variants of the problem as we focus
Externí odkaz:
http://arxiv.org/abs/2307.07782
The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretic
Externí odkaz:
http://arxiv.org/abs/2305.02059
Autor:
Ito, Takehiro, Kakimura, Naonori, Kamiyama, Naoyuki, Kobayashi, Yusuke, Maezawa, Shun-ichi, Nozaki, Yuta, Okamoto, Yoshio
We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open problem raised by Cardinal. A graph associahedron is a generalization of
Externí odkaz:
http://arxiv.org/abs/2304.14782
Autor:
Ito, Takehiro, Iwamasa, Yuni, Kobayashi, Yusuke, Maezawa, Shun-ichi, Nozaki, Yuta, Okamoto, Yoshio, Ozeki, Kenta
In 1973, Fisk proved that any $4$-coloring of a $3$-colorable triangulation of the $2$-sphere can be obtained from any $3$-coloring by a sequence of Kempe-changes. On the other hand, in the case where we are only allowed to recolor a single vertex in
Externí odkaz:
http://arxiv.org/abs/2210.17105
Autor:
Ito, Takehiro, Iwamasa, Yuni, Kakimura, Naonori, Kobayashi, Yusuke, Maezawa, Shun-ichi, Nozaki, Yuta, Okamoto, Yoshio, Ozeki, Kenta
In this paper, we consider a transformation of $k$ disjoint paths in a graph. For a graph and a pair of $k$ disjoint paths $\mathcal{P}$ and $\mathcal{Q}$ connecting the same set of terminal pairs, we aim to determine whether $\mathcal{P}$ can be tra
Externí odkaz:
http://arxiv.org/abs/2210.11778
Autor:
Ito, Takehiro, Kakimura, Naonori, Kamiyama, Naoyuki, Kobayashi, Yusuke, Nozaki, Yuta, Okamoto, Yoshio, Ozeki, Kenta
We consider the problem of determining whether a target item assignment can be reached from an initial item assignment by a sequence of pairwise exchanges of items between agents. In particular, we consider the situation where each agent has a dichot
Externí odkaz:
http://arxiv.org/abs/2209.10262
This paper collects all descriptions of solvers and ISR instances submitted to CoRe Challenge 2022.
Externí odkaz:
http://arxiv.org/abs/2208.02495
Autor:
Ito, Takehiro, Iwamasa, Yuni, Kakimura, Naonori, Kamiyama, Naoyuki, Kobayashi, Yusuke, Nozaki, Yuta, Okamoto, Yoshio, Ozeki, Kenta
We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results i
Externí odkaz:
http://arxiv.org/abs/2207.02641
Autor:
Banyassady, Bahareh, de Berg, Mark, Bringmann, Karl, Buchin, Kevin, Fernau, Henning, Halperin, Dan, Kostitsyna, Irina, Okamoto, Yoshio, Slot, Stijn
We consider the unlabeled motion-planning problem of $m$ unit-disc robots moving in a simple polygonal workspace of $n$ edges. The goal is to find a motion plan that moves the robots to a given set of $m$ target positions. For the unlabeled variant,
Externí odkaz:
http://arxiv.org/abs/2205.07777