Zobrazeno 1 - 10
of 82
pro vyhledávání: '"Kiyomi, Masashi"'
In this note, we consider the problem of finding a step-by-step transformation between two longest increasing subsequences in a sequence, namely Longest Increasing Subsequence Reconfiguration. We give a polynomial-time algorithm for deciding whether
Externí odkaz:
http://arxiv.org/abs/2310.01066
Autor:
Hanaka, Tesshu, Kiyomi, Masashi, Kobayashi, Yasuaki, Kobayashi, Yusuke, Kurita, Kazuhiro, Otachi, Yota
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 problems as objective functions and constraints are only "approximately" fo
Externí odkaz:
http://arxiv.org/abs/2201.08940
For intractable problems on graphs of bounded treewidth, two graph parameters treedepth and vertex cover number have been used to obtain fine-grained complexity results. Although the studies in this direction are successful, we still need a systemati
Externí odkaz:
http://arxiv.org/abs/2101.09414
Autor:
Aoike, Yuuki, Gima, Tatsuya, Hanaka, Tesshu, Kiyomi, Masashi, Kobayashi, Yasuaki, Kobayashi, Yusuke, Kurita, Kazuhiro, Otachi, Yota
A cactus is a connected graph that does not contain $K_4 - e$ as a minor. Given a graph $G = (V, E)$ and integer $k \ge 0$, Cactus Vertex Deletion (also known as Diamond Hitting Set) is the problem of deciding whether $G$ has a vertex set of size at
Externí odkaz:
http://arxiv.org/abs/2012.04910
We present the first $\mathrm{o}(n)$-space polynomial-time algorithm for computing the length of a longest common subsequence. Given two strings of length $n$, the algorithm runs in $\mathrm{O}(n^{3})$ time with $\mathrm{O}\left(\frac{n \log^{1.5} n}
Externí odkaz:
http://arxiv.org/abs/2009.08588
Autor:
Belmonte, Rémy, Hanaka, Tesshu, Kanzaki, Masaaki, Kiyomi, Masashi, Kobayashi, Yasuaki, Kobayashi, Yusuke, Lampis, Michael, Ono, Hirotaka, Otachi, Yota
Given a graph $G = (V,E)$, $A \subseteq V$, and integers $k$ and $\ell$, the \textsc{$(A,\ell)$-Path Packing} problem asks to find $k$ vertex-disjoint paths of length $\ell$ that have endpoints in $A$ and internal points in $V \setminus A$. We study
Externí odkaz:
http://arxiv.org/abs/2008.03448
Autor:
Belmonte, Rémy, Ghadikolaei, Mehdi Khosravian, Kiyomi, Masashi, Lampis, Michael, Otachi, Yota
Fixed-Flood-It and Free-Flood-It are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is to produce a monochromatic ("flooded") graph as quickly as possible.
Externí odkaz:
http://arxiv.org/abs/1804.08236
Publikováno v:
In Theoretical Computer Science 29 May 2022 918:60-76
Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in $O(n \log n)$ time and space. Our goal in this paper is to reduce the space consumption while keeping the t
Externí odkaz:
http://arxiv.org/abs/1712.09230
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.