Mathias Bæk Tejs Knudsen

most citedNear-Optimal Induced Universal Graphs for Bounded Degree Graphs

1 citations · 1 across the 3 of their papers we have counts for

collaborators

3 papers

cs.DS2016★ 1 cited

Near-Optimal Induced Universal Graphs for Bounded Degree Graphs

Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm +2

A graph $U$ is an induced universal graph for a family $F$ of graphs if every graph in $F$ is a vertex-induced subgraph of $U$ . For the family of all undirected graphs on $n$ verti…

cs.DS2014

A simple and optimal ancestry labeling scheme for trees

Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Noy Rotbart

We present a $l g n + 2 l g l g n + 3$ ancestry labeling scheme for trees. The problem was first presented by Kannan et al. [STOC 88'] along with a simple $2 l g n$ solution. Motivat…

cs.DS2014

Dynamic and Multi-functional Labeling Schemes

Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Noy Rotbart

We investigate labeling schemes supporting adjacency, ancestry, sibling, and connectivity queries in forests. In the course of more than 20 years, the existence of $\log n + O(\log…