Network optimization on partitioned pairs of points

DOI10.4230/LIPICS.ISAAC.2017.6MaRDI QIDQ5136221zbMATH OpenFDO

Authors Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Su Jia, Tyler Mayer, Joseph S. B. Mitchell, Matthew J. Katz

Publication date 25 November 2020

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

zbMATH Keywords

matchingNP-hardspanning treepairstraveling salesman tour

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Bichromatic 2-center of pairs of points
• Bichromatic 2-center of pairs of points
• Minimum-weight two-connected spanning networks
• scientific article; zbMATH DE number 7662164
• The 2-path network problem

Cites work

• scientific article; zbMATH DE number 1875422 (Why is no real title available?)
• Approximation algorithms for generalized MST and TSP in grid clusters
• Bichromatic 2-center of pairs of points
• Computing the smallest color-spanning axis-parallel square
• Geometric avatar problems
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Improved upper bounds for the Steiner ratio
• Introduction to algorithms
• Minimum-diameter covering problems
• New models of the generalized minimum spanning tree problem
• On the complexity of partitioning graphs into connected subgraphs
• On the generalized minimum spanning tree problem
• Relaxation methods for the Generalized Minimum Spanning Tree problem
• SMALLEST COLOR-SPANNING OBJECT REVISITED

Cited in

(4)

• Efficient points on a network
• scientific article; zbMATH DE number 7662164 (Why is no real title available?)
• Bichromatic 2-center of pairs of points
• The optimal partitioning of networks

This page was built for publication: Network optimization on partitioned pairs of points

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