Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs

DOI10.1007/BF01758842zbMath0748.68081OpenAlexW2065158139MaRDI QIDQ1194341

Chuan Yi Tang, Maw-Shang Chang, Richard Chia-Tung Lee

Publication date: 27 September 1992

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01758842

zbMATH Keywords

bottleneck optimization problemrelative neighborhood graphsEuclidean bottleneck matching problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

PROXIMITY GRAPHS: E, δ, Δ, χ AND ω ⋮ Faster bottleneck non-crossing matchings of points in convex position ⋮ Bottleneck matching in the plane ⋮ Higher-order triangular-distance Delaunay graphs: graph-theoretical properties ⋮ Approximating the bottleneck plane perfect matching of a point set ⋮ Unnamed Item ⋮ Structural properties of bichromatic non-crossing matchings ⋮ Fast algorithms for computing \(\beta\)-skeletons and their relatives. ⋮ Monochromatic plane matchings in bicolored point set ⋮ Bottleneck matchings and Hamiltonian cycles in higher-order Gabriel graphs ⋮ Computing Euclidean bottleneck matchings in higher dimensions ⋮ 10-Gabriel graphs are Hamiltonian ⋮ Optimal point movement for covering circular regions ⋮ Matchings in higher-order Gabriel graphs

Cites Work

• Unnamed Item
• Computing relative neighbourhood graphs in the plane
• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
• The relative neighbourhood graph of a finite planar set
• Algorithms for two bottleneck optimization problems