8 papers
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…
Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity
Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi +2
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 t…
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka +5
A cactus is a connected graph that does not contain as a minor. Given a graph and integer , Cactus Vertex Deletion (also known as Diamond Hitting Se…
Longest Common Subsequence in Sublinear Space
Masashi Kiyomi, Takashi Horiyama, Yota Otachi
We present the first -space polynomial-time algorithm for computing the length of a longest common subsequence. Given two strings of length , the algorithm runs i…
Parameterized Complexity of -Path Packing
Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki +6
Given a graph , , and integers and , the \textsc{-Path Packing} problem asks to find vertex-disjoint paths of length that h…
How Bad is the Freedom to Flood-It?
Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi +2
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…
Space-Efficient Algorithms for Longest Increasing Subsequence
Masashi Kiyomi, Hirotaka Ono, Yota Otachi +2
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 time and space. Our goa…
Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data
Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh
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 phyloge…