49 citations · 80 across the 23 of their papers we have counts for
5 papers · 1 filter
Algorithmic Theory of Qubit Routing
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2
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 progra…
EFX Allocations for Indivisible Chores: Matching-Based Approach
Yusuke Kobayashi, Ryoga Mahara, Souta Sakamoto
One of the most important topics in discrete fair division is whether an EFX allocation exists for any instance. Although the existence of EFX allocations is a standing open proble…
Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +4
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 pro…
An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-free Two-Edge-Cover
Yusuke Kobayashi, Takashi Noguchi
The -Edge-Connected Spanning Subgraph problem (2-ECSS) is one of the most fundamental and well-studied problems in the context of network design. In the problem, we are given an…
Reconfiguration of the Union of Arborescences
Yusuke Kobayashi, Ryoga Mahara, Tamás Schwarcz
An arborescence in a digraph is an acyclic arc subset in which every vertex execpt a root has exactly one incoming arc. In this paper, we reveal the reconfigurability of the union…