Approximating Spanning Trees with Low Crossing Number

Details Approximating Spanning Trees with Low Crossing Number Approximating Spanning Trees with Low Crossing Number

2009-07-07

arxiv.org/abs/0907.1131v1

Computer Science

Computational Geometry

Scientific paper

We present a linear programming based algorithm for computing a spanning tree $T$ of a set $P$ of $n$ points in $\Re^d$, such that its crossing number is $O(\min(t \log n, n^{1-1/d}))$, where $t$ the minimum crossing number of any spanning tree of $P$. This is the first guaranteed approximation algorithm for this problem. We provide a similar approximation algorithm for the more general settings of building a spanning tree for a set system with bounded \VC dimension. Our approach is an alternative to the reweighting technique previously used in computing such spanning trees. Our approach is an alternative to the reweighting technique previously used in computing such spanning trees.

Affiliated with

Also associated with

No associations

Rating

Approximating Spanning Trees with Low Crossing Number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximating Spanning Trees with Low Crossing Number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating Spanning Trees with Low Crossing Number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-355295