Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with sparse graphs:
TR06-089 | 16th July 2006
Sofya Raskhodnikova, Adam Smith

A Note on Adaptivity in Testing Properties of Bounded Degree Graphs

We show that in the bounded degree model for graph property testing,
adaptivity is essential. An algorithm is *non-adaptive* if it makes all queries to the input before receiving any answers. We call a property *non-trivial* if it does not depend only on the degree distribution of the nodes. We ... more >>>

TR21-114 | 29th July 2021
Henning Fernau, Kshitij Gajjar

The Space Complexity of Sum Labelling

A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider ... more >>>

ISSN 1433-8092 | Imprint