Discrete Informatics Laboratory (Mathematical Informatics Lab. 2)
Algorithms and Data Structures
We study algorithms and data structures for efficient processing of discrete data such as strings and graphs.
We consider succinct data structures which can process compressed big data without decompression,
indexing data structures for fast graph processing, etc.
We also apply those theories to practical applications such as genome informatics and geographical information systems.
We study optimization problems on discrete systems
by making full use of discrete mathematics such as graph, network, and matroid.
We also study related mathematical structures such as
convexity, symmetry, sparsity, hierarchy, and metric,
from algebraic and algorithmic point of view.
We aim at developing practical and beautiful applied mathematics.
Compressed Discrete Structure Processing based on Graph Representations
Our research motivation is to develop techniques for solving NP-hard problems or processing big data in practical situations.
Binary decision diagrams (BDDs) are ones of our favorite data structure that represent discrete structure compactly.
We present algorithms to construct compact index or enumerate all solutions efficiently for large-scale data compressed by BDDs.