Given a set of n points TeX in the plane and a real value t>1 we show how to construct in time TeX a t-spanner TeX of TeX such that there exists a set of vertices TeX of size TeX whose removal leaves two disconnected sets TeX and TeX where neither is of size greater than 2/3 · n. The spanner also has some additional properties; low weight and constant degree.
|Title of host publication||Fundamentals of Computation Theory (Proceedings 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003)|
|Editors||A. Lingas, B.J. Nilsson|
|Place of Publication||Berlin|
|Publication status||Published - 2003|
|Name||Lecture Notes in Computer Science|