Compact representation for matrices of bounded twin-width

10/15/2021

∙

by   Michał Pilipczuk, et al.

∙

0

∙

share

For every fixed d ∈ℕ, we design a data structure that represents a binary n × n matrix that is d-twin-ordered. The data structure occupies O_d(n) bits, which is the least one could hope for, and can be queried for entries of the matrix in time O_d(loglog n) per query.