The 2-radius and 2-radiian problems on trees

DOI10.1016/j.tcs.2008.08.022zbMath1216.05012OpenAlexW2021655423MaRDI QIDQ955029

Kun-Mao Chao, Hung-Lung Wang

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.08.022

zbMATH Keywords

treecentermedianradiusfacility location problemcentdianradiian

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Discrete location and assignment (90B80) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The centdian subtree on tree networks
• A linear-time algorithm for solving the center problem on weighted cactus graphs
• Minimizing the sum of the \(k\) largest functions in linear time.
• Fast Algorithms for Finding Nearest Common Ancestors
• Algorithms for finding P-centers on a weighted tree (for relatively small P)
• Medi-Centers of a Tree
• Equivalent Mathematical Programming Formulations of Monotonic Tree Network Location Problems
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Duality in the Cent-Dian of a Graph
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• Finding Minimal Center-Median Convex Combination (Cent-Dian) of a Graph
• Spanning Trees and Optimization Problems
• A polynomial algorithm for thep-centdian problem on a tree
• Computing the 2‐median on tree networks in O(n lg n) time
• The backup 2‐center and backup 2‐median problems on trees
• Locating Facilities on a Network to Minimize Their Average Service Radius
• Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph Radii
• Algorithms and Computation