scientific article; zbMATH DE number 871938

zbMATH Open0857.90129MaRDI QIDQ4875213FDOQ4875213

Authors: Joseph S. B. Mitchell 

Publication date: 18 June 1996

Title of this publication is not available (Why is that?)

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

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)

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)