Improved algorithms for some competitive location centroid problems on paths, trees and graphs

DOI10.1007/S00453-012-9655-1zbMath1266.90118OpenAlexW2038526704MaRDI QIDQ2375952

Avivit Lazar, Arie Tamir

Publication date: 25 June 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9655-1

zbMATH Keywords

pathstreespolynomial algorithmscentroidscompetitive location problems

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Applications of graph theory (05C90) Discrete location and assignment (90B80)

Related Items (3)

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees ⋮ The nestedness property of location problems on the line ⋮ On fixed-parameter solvability of the minimax path location problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multiple voting location and single voting location on trees
• An \(O(n(\log n)^{2}/\log \log n)\) algorithm for the single maximum coverage location or the \((1,X_p)\)-medianoid problem on trees
• \((r,p)\)-centroid problems on paths and trees
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• On locating new facilities in a competitive environment
• Sequential location problems
• The least element property of center location on tree networks with applications to distance and precedence constrained problems
• A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
• Time bounds for selection
• Some APX-completeness results for cubic graphs
• Tree-width, path-width, and cutwidth
• Relaxation of the Condorcet and Simpson conditions in voting location
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems
• The Maximum Coverage Location Problem
• Algorithms for finding P-centers on a weighted tree (for relatively small P)
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Block-vertex duality and the one-median problem
• Algorithms for Voting and Competitive Location on a Network
• Combinatorial Optimization with Rational Objective Functions
• 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
• Fibonacci heaps and their uses in improved network optimization algorithms

This page was built for publication: Improved algorithms for some competitive location centroid problems on paths, trees and graphs