EDBT 2026 Demo / reviewers in the wild / expert
Masaaki Kanzaki
dblp:266/2235
· DBLP profile ↗
4ranked-venue papers
2as first author
3since 2021 · last 2024
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 4 · 2 first-author · 3 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2024 | Computational complexity of jumping block puzzles
Masaaki Kanzaki, Yota Otachi, Giovanni Viglietta, Ryuhei Uehara |
Theor. Comput. Sci. | 1 |
| 2022 | Parameterized Complexity of (A, ℓ )-Path PackingabstractAbstract Given a graph $$G = (V,E)$$ G = ( V , E ) , $$A \subseteq V$$ A ⊆ V , and integers k and $$\ell $$ ℓ , the $$(A,\ell )$$ ( A , ℓ ) -Path Packing problem asks to find k vertex-disjoint paths of length exactly $$\ell $$ ℓ that have endpoints in A and internal points in $$V{\setminus }A$$ V \ A . We study the parameterized complexity of this problem with parameters |A|, $$\ell $$ ℓ , k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when $$\ell \le 3$$ ℓ ≤ 3 , while it is NP-complete for constant $$\ell \ge 4$$ ℓ ≥ 4 . We also show that the problem is W[1]-hard parameterized by pathwidth $${}+|A|$$ + | A | , while it is fixed-parameter tractable parameterized by treewidth $${}+\ell $$ + ℓ . Additionally, we study a variant called Short A-Path Packing that asks to find k vertex-disjoint paths of length at most $$\ell $$ ℓ . We show that all our positive results on the exact-length version can be translated to this version and show the hardness of the cases where |A| or $$\ell $$ ℓ is a constant. Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi 0001, Michael Lampis, Hirotaka Ono 0001, Yota Otachi |
Algorithmica | 3 |
| 2021 | Computational Complexity of Jumping Block Puzzles
Masaaki Kanzaki, Yota Otachi, Ryuhei Uehara |
COCOON | 1 |
| 2020 | Parameterized Complexity of (A, ℓ )-Path Packing
Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi 0001, Michael Lampis, Hirotaka Ono 0001, Yota Otachi |
IWOCA | 3 |