Fast geometric approximation techniques and geometric embedding problems
From MaRDI portal
Publication:1202926
DOI10.1016/0304-3975(92)90252-BzbMath0776.05034MaRDI QIDQ1202926
Howard J. Karloff, Baruch Schieber, Prabhakar Raghavan, Marshall W. Bern
Publication date: 22 April 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
treesortingapproximationminimum spanning treestarplanefast approximation algorithmsgeometric embedding problems
Trees (05C05) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items
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?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graphs whose every transitive orientation contains almost every relation
- On optimal linear arrangements of trees
- Upper bounds for sorting integers on random access machines
- Sorting helps for Voronoi diagrams
- Approximate minimum weight matching on points in k-dimensional space
- Wafer-Scale Integration of Systolic Arrays
- Minimum Spanning Trees in k-Dimensional Space
- Approximation algorithms for convex hulls
- The complexity of restricted spanning tree problems
- Design and implementation of an efficient priority queue
- Fibonacci heaps and their uses in improved network optimization algorithms