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

DOI10.1016/0166-218X(92)90111-MMaRDI QIDQ1199461zbMATH OpenOpenAlexFDO

Authors Chuan Yi Tang, Maw-Shang Chang, R. C. T. Lee

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

algorithmbiconnectivitybinary search techniqueEuclidean bottleneck biconnected edge subgraph problemrelative neighborhood graphtime complexity

Mathematics Subject Classification ID

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

Recommendations

• Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs
• On exact solutions to the Euclidean bottleneck Steiner tree problem
• A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem
• The bottleneck 2-connected k-Steiner network problem for k 2
• A linear time algorithm for the bottleneck biconnected spanning subgraph problem

Cites work

• Bottleneck extrema
• Computing relative neighbourhood graphs in the plane
• Finding EPS-graphs
• Guaranteed performance heuristics for the bottleneck traveling salesman problem
• scientific article; zbMATH DE number 3898613 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 403946 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• The Bottleneck Traveling Salesman Problem
• The relative neighbourhood graph of a finite planar set

Cited in

(11)

• Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs
• A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem
• Minmax regret solutions for minimax optimization problems with uncertainty
• A linear time algorithm for the bottleneck biconnected spanning subgraph problem
• The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation
• The bottleneck 2-connected k-Steiner network problem for k 2
• Proximity graphs: {\(E, \delta\)}, {\(\Delta\)}, {\(\chi\)} and {\(\omega\)}
• Fixed parameter tractability of a biconnected bottleneck Steiner network problem
• 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

This page was built for publication: Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs

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