Improved Spanning Ratio for Low Degree Plane Spanners
classification
💻 cs.CG
keywords
degreeplaneratiospanningmaximumspanneralgorithmapproximately
read the original abstract
We describe an algorithm that builds a plane spanner with a maximum degree of 8 and a spanning ratio of approximately 4.414 with respect to the complete graph. This is the best currently known spanning ratio for a plane spanner with a maximum degree of less than 14.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.