Fast geometric approximation techniques and geometric embedding problems

DOI10.1016/0304-3975(92)90252-BMaRDI QIDQ1202926zbMATH OpenFDO

Authors Howard Karloff, Prabhakar Raghavan, Baruch Schieber, M. W. Bern

Publication date 22 April 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

treeminimum spanning treeapproximationsortingstarplanefast approximation algorithmsgeometric embedding problems

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• A fast and simple algorithm for computing approximate Euclidean minimum spanning trees
• Faster geometric \(k\)-point MST approximation
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Minimum Spanning Trees in k-Dimensional Space
• scientific article; zbMATH DE number 1775442

Cites work

• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 4064519 (Why is no real title available?)
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Approximate minimum weight matching on points in k-dimensional space
• Approximation algorithms for convex hulls
• Design and implementation of an efficient priority queue
• Fibonacci heaps and their uses in improved network optimization algorithms
• Graphs whose every transitive orientation contains almost every relation
• Minimum Spanning Trees in k-Dimensional Space
• On optimal linear arrangements of trees
• Sorting helps for Voronoi diagrams
• The complexity of restricted spanning tree problems
• Upper bounds for sorting integers on random access machines
• Wafer-Scale Integration of Systolic Arrays

Cited in

(4)

• Two results on linear embeddings of complete binary trees
• Optimal point-set embedding of wheel graphs and a sub-class of 3-trees
• Combinatorial theorems about embedding trees on the real line
• Well-separated pair decomposition in linear time?

This page was built for publication: Fast geometric approximation techniques and geometric embedding problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1202926)