77 citations
- Shibuya (Japan)JP7 papers
- The University of TokyoJP5 papers
- Cornell UniversityUS3 papers
- Waseda UniversityJP3 papers
- Yokohama National UniversityJP3 papers
- Nagoya UniversityJP2 papers
- National Institute of InformaticsJP2 papers
- The University of OsakaJP2 papers
- University of Southern CaliforniaUS2 papers
- Yale UniversityUS2 papers
- Anthem (United States)US1 paper
- Bunkyo UniversityJP1 paper
4 papers · 1 filter
Dichotomies for Tree Minor Containment with Structural Parameters
Tatsuya Gima, Soh Kumabe, Kazuhiro Kurita +2
The problem of determining whether a graph contains another graph as a minor, referred to as the minor containment problem, is a fundamental problem in the field of graph a…
On the Parameterized Intractability of Determinant Maximization
Naoto Ohsaka
In the Determinant Maximization problem, given an positive semi-definite matrix in and an integer , we are required to find a $k\ti…
Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes
Naoto Ohsaka
We study the computational complexity of two hard problems on determinantal point processes (DPPs). One is maximum a posteriori (MAP) inference, i.e., to find a principal submatrix…
On Reconfigurability of Target Sets
Naoto Ohsaka
We study the problem of deciding reconfigurability of target sets of a graph. Given a graph with vertex thresholds , consider a dynamic process in which vertex becomes a…