Zobrazeno 1 - 10
of 78
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
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.
We study a character-based phylogeny reconstruction problem when an incomplete set of data is given. More specifically, we consider the situation under the directed perfect phylogeny assumption with binary characters in which for some species the sta
Externí odkaz:
http://arxiv.org/abs/1203.3284