5 papers
Revisiting the Sparse Matrix Compression Problem
Vincent Jugé, Dominik Köppl, Vincent Limouzy +4
The sparse matrix compression problem asks for a one-dimensional representation of a binary matrix, formed by an integer array of row indices and a shift function f…
Finding Diverse Strings and Longest Common Subsequences in a Graph
Yuto Shida, Giulia Punzi, Yasuaki Kobayashi +2
In this paper, we study for the first time the Diverse Longest Common Subsequences (LCSs) problem under Hamming distance. Given a set of a constant number of input strings, the pro…
Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size
Alessio Conte, Roberto Grossi, Yasuaki Kobayashi +4
Graphlets of order in a graph are connected subgraphs induced by nodes (called -graphlets) or by edges (called edge -graphlets). They are among the interestin…
Parameterized Complexity of Finding Dissimilar Shortest Paths
Ryo Funayama, Yasuaki Kobayashi, Takeaki Uno
We consider the problem of finding ``dissimilar'' shortest paths from to in an edge-weighted directed graph , where the dissimilarity is measured by the minimum pair…
The Algebraic Combinatorial Approach for Low-Rank Matrix Completion
Franz J. Király, Louis Theran, Ryota Tomioka
We present a novel algebraic combinatorial view on low-rank matrix completion based on studying relations between a few entries with tools from algebraic geometry and matroid theor…