8 citations · 36 across the 49 of their papers we have counts for
7 papers · 1 filter
On the Complexity of Forcing and Anti-Forcing Minimum Cuts
Tatsuya Gima, Yasuaki Kobayashi, Hiraku Morimoto +1
For an instance of a combinatorial optimization problem, a \emph{forcing set} is a set of elements such that there is a unique optimal solution including it. Symmetrically, an \emp…
Complexity of induced subgraph isomorphism and maximum common induced subgraph parameterized by cluster vertex deletion number
Tomohiro Koana, Soh Kumabe, Yota Otachi
We study the parameterized complexity of Induced Subgraph Isomorphism (ISI) and Maximum Common Induced Subgraph (MCIS) with respect to the cluster vertex deletion number . For I…
3-packings in Triangulations: Algorithms, bounds, and Complexity
Prosenjit Bose, Anil Maheshwari, Bobby Miraftab +1
We study -packings in plane triangulations for the three-vertex graphs . For a graph , let denote the maximum size of an -packing in…
Treewidth of the toroidal grid
Tatsuya Gima, Hiraku Morimoto, Yuto Okada +1
In this paper, we show that the treewidth of the toroidal grid is for all . This closes the gap between the previously known upper bound of (Ell…
Biclique Reconfiguration in Bipartite Graphs
Yota Otachi, Emi Toyoda
We prove that Balanced Biclique Reconfiguration on bipartite graphs is PSPACE-complete. This implies the PSPACE-completeness of the spanning variant of Subgraph Reconfiguration und…
Spanning tree congestion of proper interval graphs
Yota Otachi
We show that the spanning tree congestion problem is NP-complete even on proper interval graphs with linear clique-width at most 4 and diameter 3. By slightly modifying the reducti…
On Edge-Disjoint Maximal Outerplanar Graphs
Yuto Okada, Yota Otachi, Lena Volk
We provide two constructions for edge-disjoint maximal outerplanar graphs on every number of vertices. The bound on the minimum number of vertices is tight. These c…