Improved algorithms for some competitive location centroid problems on paths, trees and graphs
From MaRDI portal
Publication:2375952
DOI10.1007/s00453-012-9655-1zbMath1266.90118OpenAlexW2038526704MaRDI QIDQ2375952
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
Analysis of algorithms (68W40) Applications of graph theory (05C90) Discrete location and assignment (90B80)
Related Items
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
