On minimum- and maximum-weight minimum spanning trees with neighborhoods

DOI10.1007/s00224-014-9591-3zbMath1328.68261OpenAlexW2036493899MaRDI QIDQ2344217

Diego Seco, Meng He, Akitoshi Kawamura, Shahin Kamali, Reza Dorrigiv, Alejandro López-Ortiz, Robert Fraser

Publication date: 12 May 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-014-9591-3

zbMATH Keywords

computational geometryminimum spanning treesimprecise data

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Facility location problems on graphs with non-convex neighborhoods ⋮ Ordered \(p\)-median problems with neighbourhoods ⋮ On hub location problems in geographically flexible networks ⋮ Query-competitive algorithms for cheapest set problems under uncertainty ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Euclidean minimum spanning trees with independent and dependent geometric uncertainties ⋮ On the longest spanning tree with neighborhoods ⋮ Minimum cost \(b\)-matching problems with neighborhoods

Cites Work

• Unnamed Item
• Area-efficient static and incremental graph drawings
• Largest and smallest convex hulls for imprecise points
• The projection median of a set of points
• The algebraic degree of geometric optimization problems
• Approximation algorithms for the Geometric Covering Salesman Problem
• Systems of distant representatives
• Connectivity graphs of uncertainty regions
• n-Ellipses and the Minimum Distance Sum Problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Planar Formulae and Their Uses
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• Approximation algorithms for TSP with neighborhoods in the plane
• On the History of the Minimum Spanning Tree Problem
• Minimum Spanning Tree with Neighborhoods
• TSP with neighborhoods of varying size