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

DOI10.1007/S00453-012-9655-1zbMATH Open1266.90118OpenAlexW2038526704MaRDI QIDQ2375952FDOQ2375952

Authors: 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

Recommendations

• \((r,p)\)-centroid problems on paths and trees
• A branch-and-cut algorithm for the discrete \((r| p)\)-centroid problem
• The \((1 | 1)\)-centroid problem in the plane with distance constraints
• The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints
• scientific article; zbMATH DE number 1323029

zbMATH Keywords

treespathspolynomial algorithmscentroidscompetitive location problems

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• \((r|p)\)-centroid problems on networks with vertex and edge demand
• A quadratic time exact algorithm for continuous connected 2-facility location problem in trees
• An improved algorithm for the \(p\)-center problem on interval graphs with unit lengths
• On locating new facilities in a competitive environment
• Title not available (Why is that?)
• Relaxed voting and competitive location under monotonous gain functions on trees
• A competitive facility location problem on a tree network with stochastic weights.
• On fixed-parameter solvability of the minimax path location problem
• The \((1 | 1)\)-centroid problem in the plane with distance constraints
• The nestedness property of location problems on the line
• Traveling salesmen in the presence of competition

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2375952)