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)

Full work available at URL https://doi.org/10.1016/0304-3975(92)90252-B

zbMATH Keywords

approximationfast approximation algorithmsgeometric embedding problemsminimum spanning treeplanesortingstartree

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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

(5)

• 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
• A linear-time approximation algorithm for the minimum-length geometric embedding of trees
• 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)