49 citations · 80 across the 23 of their papers we have counts for
6 papers · 1 filter
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka +5
A cactus is a connected graph that does not contain as a minor. Given a graph and integer , Cactus Vertex Deletion (also known as Diamond Hitting Se…
Fixed-Parameter Algorithms for Graph Constraint Logic
Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito +3
Non-deterministic constraint logic (NCL) is a simple model of computation based on orientations of a constraint graph with edge weights and vertex demands. NCL captures \PSPACE\xsp…
Finding a Maximum Minimal Separator: Graph Classes and Fixed-Parameter Tractability
Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi +1
We study the problem of finding a maximum cardinality minimal separator of a graph. This problem is known to be NP-hard even for bipartite graphs. In this paper, we strengthen this…
Market Pricing for Matroid Rank Valuations
Kristóf Bérczi, Naonori Kakimura, Yusuke Kobayashi
In this paper, we study the problem of maximizing social welfare in combinatorial markets through pricing schemes. We consider the existence of prices that are capable to achieve o…
Reconfiguration of Spanning Trees with Many or Few Leaves
Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi +4
Let be a graph and be two spanning trees of . We say that can be transformed into via an edge flip if there exist two edges and in $T_2…
Envy-free Relaxations for Goods, Chores, and Mixed Items
Kristóf Bérczi, Erika R. Bérczi-Kovács, Endre Boros +5
In fair division problems, we are given a set of items and a set of agents with individual preferences, and the goal is to find an allocation of items among agents…