Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs

DOI10.1016/0166-218X(92)90111-MzbMath0768.68125OpenAlexW2136875057MaRDI QIDQ1199461

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

Publication date: 16 January 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(92)90111-m

zbMATH Keywords

algorithmtime complexitybiconnectivityrelative neighborhood graphbinary search techniqueEuclidean bottleneck biconnected edge subgraph problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)

Related Items

A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem ⋮ PROXIMITY GRAPHS: E, δ, Δ, χ AND ω ⋮ Fixed parameter tractability of a biconnected bottleneck Steiner network problem ⋮ The bottleneck 2-connected \(k\)-Steiner network problem for \(k \leq 2\) ⋮ Survivable minimum bottleneck networks ⋮ Higher-order triangular-distance Delaunay graphs: graph-theoretical properties ⋮ An exact algorithm for the bottleneck 2-connected \(k\)-Steiner network problem in \(L_p\) planes ⋮ A linear time algorithm for the bottleneck biconnected spanning subgraph problem ⋮ Minmax regret solutions for minimax optimization problems with uncertainty

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Guaranteed performance heuristics for the bottleneck traveling salesman problem
• Computing relative neighbourhood graphs in the plane
• The relative neighbourhood graph of a finite planar set
• Finding EPS-graphs
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• The Bottleneck Traveling Salesman Problem
• Bottleneck extrema