Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
An Expansion Tester for Bounded Degree Graphs
verfasst von : Satyen Kale, C. Seshadhri
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the problem of testing graph expansion (either vertex or edge) in the bounded degree model [10]. We give a property tester that given a graph with degree bound
d
, an expansion bound
α
, and a parameter
ε
> 0, accepts the graph with high probability if its expansion is more than
α
, and rejects it with high probability if it is
ε
-far from any graph with expansion
α
′ with degree bound
d
, where
α
′ <
α
is a function of
α
. For edge expansion, we obtain
$\alpha' = \Omega(\frac{\alpha^2}{d})$
, and for vertex expansion, we obtain
$\alpha' = \Omega(\frac{\alpha^2}{d^2})$
. In either case, the algorithm runs in time
$\tilde{O}(\frac{n^{(1+\mu)/2}d^2}{\epsilon\alpha^2})$
for any given constant
μ
> 0.