Almost All Even Yao-Yao Graphs Are Spanners

Abstract: It is an open problem whether Yao-Yao graphs

m a t h s f {Y Y}_{k}

(also known as sparse-Yao graphs) are all spanners when the integer parameter

k

is large enough. In this paper we show that, for any integer

k g e q 42

, the Yao-Yao graph

m a t h s f {Y Y}_{2 k}

is a

t_{k}

-spanner, with stretch factor

t_{k} = 6.03 + O (k^{- 1})

when

k

tends to infinity. Our result generalizes the best known result which asserts that all

m a t h s f {Y Y}_{6 k}

are spanners for

k

large enough [Bauer and Damian, SODA'13]. Our proof is also somewhat simpler.

Recommendations

Cited In (7)

This page was built for publication: Almost All Even Yao-Yao Graphs Are Spanners