Locating Facilities on a Network to Minimize Their Average Service Radius

DOI10.1007/978-3-540-77120-3_51zbMath1193.90142OpenAlexW1481887094MaRDI QIDQ5387793

Luciano Gualà, Guido Proietti, Jörg Derungs, Davide Bilò, Peter Widmayer

Publication date: 27 May 2008

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

Full work available at URL: https://doi.org/10.1007/978-3-540-77120-3_51

zbMATH Keywords

NP-hardnessGraph partitionFacility location problemsGraph radiusGraph treewidth

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Discrete location and assignment (90B80)

Related Items (1)

The 2-radius and 2-radiian problems on trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clustering to minimize the sum of cluster diameters
• Polynomial time approximation schemes for base station coverage with minimum total radii
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• New Results on the Complexity of p-Centre Problems
• Graph minors. II. Algorithmic aspects of tree-width
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• A linear time algorithm for finding tree-decompositions of small treewidth
• Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph Radii
• Algorithms – ESA 2005

This page was built for publication: Locating Facilities on a Network to Minimize Their Average Service Radius