Optimal algorithms for the path/tree-shaped facility location problems in trees

DOI10.1007/s00453-007-9157-8zbMath1185.68461OpenAlexW2094293456MaRDI QIDQ1031869

Qiaosheng Shi, Binay K. Bhattacharya, Arie Tamir

Publication date: 23 October 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9157-8

zbMATH Keywords

subgraphsparametric-pruning method

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Discrete location and assignment (90B80) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Efficient algorithms for the minmax regret path center problem with length constraint on trees, A quadratic time exact algorithm for continuous connected 2-facility location problem in trees, Extensive facility location problems on networks: an updated review, The nestedness property of location problems on the line, On fixed-parameter solvability of the minimax path location problem, The extensive 1-median problem with radius on networks, An improved algorithm for the minmax regret path center problem on trees, An algorithm for solving the bi-objective median path-shaped facility on a tree network, Minimax regret path location on trees

Cites Work

• Unnamed Item
• Unnamed Item
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• A review of extensive facility location in networks
• The centdian subtree on tree networks
• On locating path- or tree-shaped facilities on networks
• Technical Note—Conditional Location Problems on Networks
• An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Algorithms for finding P-centers on a weighted tree (for relatively small P)
• The optimal location of a path or tree in a tree network
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• Finding kth paths and p-centers by generating and searching good data structures
• Efficient Parallel Algorithms for Optimally Locating a Path and a Tree of a Specified Length in a Weighted Tree Network
• Conditional location of path and tree shaped facilities on trees
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph