Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph Radii

DOI10.1007/11940128_58zbMATH Open1135.68524OpenAlexW2145630038MaRDI QIDQ5459152FDOQ5459152

Authors: Guido Proietti, Peter Widmayer 

Publication date: 24 April 2008

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11940128_58

Recommendations

• Locating Facilities on a Network to Minimize Their Average Service Radius
• The 2-radius and 2-radiian problems on trees
• scientific article; zbMATH DE number 867650
• Approximation algorithms for clustering to minimize the sum of diameters
• Partitioning a graph into connected components with fixed centers and optimizing cost-based objective functions or equipartition criteria

zbMATH Keywords

NP-hardnessGraph partitionFacility location problemsGraph radiusClustering problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Discrete location and assignment (90B80)

Cited In (6)

• Approximating fair \(k\)-min-sum-radii in Euclidean space
• Title not available (Why is that?)
• The 2-radius and 2-radiian problems on trees
• Title not available (Why is that?)
• Dynamic clustering to minimize the sum of radii
• Locating Facilities on a Network to Minimize Their Average Service Radius

This page was built for publication: Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph Radii

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