Abstract
A Bottleneck optimization problem on general graphs with edge costs is theproblem of finding a subgraph of a certain kind that minimizes the mzximumedge cost in the subgraph. a Euclidean bottleneck optimization problem isa bottleneck optimization problem on complete graphs which are constructedfrom a set of points in the plane and whose edge cost are Euclideandistances between points connected by edges. In this dissertation, wedefine a special graph called k7 relative Neighborhood Graph, denoted askRNG, where k is a positive number, and use it to solve the followingthree Euclidean bottleneck optimization problems:(A) The Euclidean bottleneck matching problem.(B) The Euclidean bottleneck biconnected edge subgraph problem.(C) The Euclidean bottleneck traveling salesperson problem.We prove the following three theorems:(1) For any instance of Problem A, there exists an optimal solution which is a subgraph of a 17RNG.(2) For any instance of Problem A, there exists an optimal solution which is a subgraph of a 2RNG.(3) For any instance of Problem A, there exists an optimal solution which is a subgraph of a 20RNG.All numbers of edges of these three special graphs are O(n). Therefore wecan find optimal solutions for the above three problems from threek7 relative neighborhood graphs. In this way, we can solve Problem A andProblem B in O(n2)time, and also an efficient approximation algorithm forProblem C is developed. The third theorem above gives us an interestinggraph theoretic result: 20RNGs are Hamiltonian.