Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
Randomized Communication and Implicit Graph Representations
Nathaniel Harms, Sebastian Wild, Viktor Zamaraev
We initiate the focused study of constant-cost randomized communication, with emphasis on its connection to graph representations. We observe that constant-cost randomized communic…
cs.DS2024
Symmetric-Difference (Degeneracy) and Signed Tree Models
Ãdouard Bonnet, Julien Duron, John Sylvester +1
We introduce a dense counterpart of graph degeneracy, which extends the recently-proposed invariant symmetric difference. We say that a graph has sd-degeneracy (for symmetric-diffe…
cs.DS2024
Optimal Adjacency Labels for Subgraphs of Cartesian Products
Louis Esperet, Nathaniel Harms, Viktor Zamaraev
For any hereditary graph class , we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in . As a…