scientific article; zbMATH DE number 7662164

DOI10.57717/CGT.V1I1.17MaRDI QIDQ5881545zbMATH OpenFDO

Authors Ahmad Biniaz, Anil Maheshwari, Michiel Smid

Publication date 10 March 2023

Full work available at URL https://arxiv.org/abs/2111.05780

zbMATH Keywords

approximation algorithmsbottleneck spanning treesmetric spaceNP-hardnesspartitioned point sets

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Continuous bottleneck tree partitioning problems
• Minimum bottleneck spanning trees with degree bounds
• Approximation algorithms for minimum tree partition
• Optimal and approximate bottleneck Steiner trees
• Euclidean bottleneck bounded-degree spanning tree ratios

Cites work

• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
• A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• A PTAS for TSP with neighborhoods among fat regions in the plane
• Algorithms and Computation
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Approximation algorithms for generalized MST and TSP in grid clusters
• Approximation algorithms for maximally balanced connected graph partition
• Approximation and inaproximability results on balanced connected partitions of graphs
• BALANCED PARTITION OF MINIMUM SPANNING TREES
• Graph theory with applications
• Graphs with 1-hamiltonian-connected cubes
• Hamiltonian paths in the square of a tree
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 7662164 (Why is no real title available?)
• Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods
• Minimum-diameter covering problems
• Minmax subtree cover problem on cacti
• Minmax tree cover in the Euclidean space
• Network optimization on partitioned pairs of points
• On minimum- and maximum-weight minimum spanning trees with neighborhoods
• On Representatives of Subsets
• On the complexity of partitioning graphs into connected subgraphs
• On the Cube of a Graph
• On the generalized minimum spanning tree problem
• Polylogarithmic inapproximability
• Relaxation methods for the Generalized Minimum Spanning Tree problem
• Selecting and covering colored points
• Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs
• Survivable networks, linear programming relaxations and the parsimonious property
• The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances
• The Min-Max Spanning Tree Problem and some extensions

Cited in

(2)

• Network optimization on partitioned pairs of points
• scientific article; zbMATH DE number 7662164 (Why is no real title available?)

This page was built for publication:

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