scientific article; zbMATH DE number 871938

MaRDI QIDQ4875213zbMATH OpenFDO

Authors Joseph S. B. Mitchell

Publication date 18 June 1996

zbMATH Keywords

minimum spanning treegeometric network designguillotine subdivisionrectilinear polygonal subdivision

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Applications of design theory to circuits and networks (94C30)

Recommendations

• A Constant-Factor Approximation Algorithm for the Geometrick-MST Problem in the Plane
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• scientific article; zbMATH DE number 1263205
• Faster geometric \(k\)-point MST approximation

Cited in

(10)

• Shape rectangularization problems in intensity-modulated radiation therapy
• An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane
• Faster geometric \(k\)-point MST approximation
• Improved bounds for vehicle routing solutions
• A constant-factor approximation algorithm for the \(k\)-MST problem
• Local search algorithms for the \(k\)-cardinality tree problem.
• Approximation algorithms for lawn mowing and milling
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• Approximation schemes for node-weighted geometric Steiner tree problems
• Probabilistic Analysis of Unit-Demand Vehicle Routeing Problems

This page was built for publication:

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