Tatsuya Gima

collaborators

3 papers

cs.DS2024

Computing diverse pair of solutions for tractable SAT

Tatsuya Gima, Yuni Iwamasa, Yasuaki Kobayashi +3

In many decision-making processes, one may prefer multiple solutions to a single solution, which allows us to choose an appropriate solution from the set of promising solutions tha…

math.CO2024

An improved spectral lower bound of treewidth

Tatsuya Gima, Tesshu Hanaka, Kohei Noro +2

We show that for every $n$ -vertex graph with at least one edge, its treewidth is greater than or equal to $n λ_{2} / (Δ + λ_{2}) - 1$ , where $Δ$ and $λ_{2}$ are the maximum degree a…

cs.DS2023

Minimum Consistent Subset for Trees Revisited

Hiroki Arimura, Tatsuya Gima, Yasuaki Kobayashi +2

In a vertex-colored graph $G = (V, E)$ , a subset $S \subseteq V$ is said to be consistent if every vertex has a nearest neighbor in $S$ with the same color. The problem of computin…