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

DOI10.1016/0020-0190(94)00041-7zbMath0814.68099MaRDI 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 algorithms; biconnectivity; biconnected spanning subgraph; bottleneck TSP problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

Related Items

Minmax regret solutions for minimax optimization problems with uncertainty, A linear time algorithm for the bottleneck biconnected spanning subgraph problem, A fast algorithm for a class of bottleneck problems, An efficient heuristic algorithm for the bottleneck traveling salesman problem

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