8 citations · 36 across the 49 of their papers we have counts for
5 papers · 1 filter
Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita +2
Finding diverse solutions in combinatorial problems recently has received considerable attention (Baste et al. 2020; Fomin et al. 2020; Hanaka et al. 2021). In this paper we study…
Reconfiguration of Regular Induced Subgraphs
Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi +2
We study the problem of checking the existence of a step-by-step transformation of -regular induced subgraphs in a graph, where and each step in the transformation mus…
Computational Complexity of Jumping Block Puzzles
Masaaki Kanzaki, Yota Otachi, Ryuhei Uehara
In combinatorial reconfiguration, the reconfiguration problems on a vertex subset (e.g., an independent set) are well investigated. In these problems, some tokens are placed on a s…
Reconfiguring (non-spanning) arborescences
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi +3
In this paper, we investigate the computational complexity of subgraph reconfiguration problems in directed graphs. More specifically, we focus on the problem of reconfiguring arbo…
Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity
Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi +2
For intractable problems on graphs of bounded treewidth, two graph parameters treedepth and vertex cover number have been used to obtain fine-grained complexity results. Although t…