From the 1 of 15 linked papers with an AI index.
15 papers
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…
Spanning tree congestion of proper interval graphs
Yota Otachi
The paper proves that the spanning tree congestion problem is NP‑complete even on proper interval graphs with linear clique‑width at most 4 and diameter 3, and extends the hardness…
Frameworks to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi +4
Finding a \emph{single} best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world probl…
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…
Parameterized Spanning Tree Congestion
Michael Lampis, Valia Mitsou, Edouard Nemery +3
In this paper we study the Spanning Tree Congestion problem, where we are given a graph and are asked to find a spanning tree of minimum maximum congestion. Here, the…
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…