2 papers
cs.DS2023
Cell-Probe Lower Bound for Accessible Interval Graphs
Sankardeep Chakraborty, Christian Engels, Seungbum Jo +1
We spot a hole in the area of succinct data structures for graph classes from a universe of size at most . Very often, the input graph is labeled by the user in an arbitrary a…
cs.CC2014
Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
Christian Engels
In this paper, we will show dichotomy theorems for the computation of polynomials corresponding to evaluation of graph homomorphisms in Valiant's model. We are given a fixed graph…