A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem

DOI10.1016/0020-0190(94)00041-7zbMath0814.68099OpenAlexW1999230121WikidataQ127872253 ScholiaQ127872253MaRDI QIDQ1329426

K. P. K. Nair, Abraham P. Punnen

Publication date: 12 June 1995

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00041-7

zbMATH Keywords

approximation algorithmsbiconnectivitybiconnected spanning subgraphbottleneck TSP problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis ⋮ A fast algorithm for a class of bottleneck problems ⋮ The bottleneck 2-connected \(k\)-Steiner network problem for \(k \leq 2\) ⋮ Experimental analysis of heuristics for the bottleneck traveling salesman problem ⋮ An efficient heuristic algorithm for the bottleneck traveling salesman problem ⋮ A linear time algorithm for the bottleneck biconnected spanning subgraph problem ⋮ Minmax regret solutions for minimax optimization problems with uncertainty

Cites Work

• Unnamed Item
• Guaranteed performance heuristics for the bottleneck traveling salesman problem
• Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs
• Traveling salesman problem under categorization
• The Min-Max Spanning Tree Problem and some extensions
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• The Bottleneck Traveling Salesman Problem
• Depth-First Search and Linear Graph Algorithms