18 citations · 26 across the 16 of their papers we have counts for
20 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…
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…
Rerouting Planar Curves and Disjoint Paths
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura +5
In this paper, we consider a transformation of disjoint paths in a graph. For a graph and a pair of disjoint paths and connecting the same set o…
Optimal General Factor Problem and Jump System Intersection
Yusuke Kobayashi
In the optimal general factor problem, given a graph and a set of integers for each , we seek for an edge subset of maximum cardi…
Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint
Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi +4
We investigate the complexity of finding a transformation from a given spanning tree in a graph to another given spanning tree in the same graph via a sequence of edge flips. The e…
An Additive Approximation Scheme for the Nash Social Welfare Maximization with Identical Additive Valuations
Asei Inoue, Yusuke Kobayashi
We study the problem of efficiently and fairly allocating a set of indivisible goods among agents with identical and additive valuations for the goods. The objective is to maximize…