Finite Dominating Sets for Network Location Problems
The paper deals with location problems with the goal to place a given number of servers at nodes or arcs of some network to minimize a cost function. The cost function depends on the distances between node and server locations or between different server locations. The authors aim at answering the question whether there is any finite set of locations in the network to which some optimal solution of the location problem must belong. Such a set of points is called finite dominating set (FDS) and its specification enables to construct an effective algorithm for the solution of the location problem. The paper contains a large survey of previous results and provides a comprehensive theory on this topic. The theory is based on 1-dominance which is a property of a large set of cost functions. This property is used in the theory to prove that FDS for easy solvable 1-server problem is FDS for \(p\)-server problem as well. Most of the previous results and their further generalization presented in the paper follows the 1-dominance and the appropriate theorems. Using the theory it is possible to get FDS easily for the generalized \(p\)- median problem, the generalized \(p\)-center problem, the generalized cent- dian problem and for the generalized obnoxious 1-center problem.
- Aggregation error for location models: Survey and analysis
- Fuzzy location problems on networks.
- A note on the location of an obnoxious facility on a network
- A general approach for the location of transfer points on a network with a trip covering criterion and mixed distances
- Infrastructure development for conversion to environmentally friendly fuel
- Algorithmic results for ordered median problems
- A framework for demand point and solution space aggregation analysis for location models
- Planar multifacility location problems with tree structure and finite dominating sets
- On the roots of domination polynomials
- The conditional \(p\)-dispersion problem
- A memetic algorithm based on reformulation local search for minimum sum-of-squares clustering in networks
- Variable neighborhood search for minimum sum-of-squares clustering on networks
- A note on the subtree ordered median problem in networks based on nestedness property
- A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem
- An optimal locating-dominating set in the infinite triangular grid
- A generalized model of equality measures in network location problems
- The \(p\)-facility ordered median problem on networks
- Unreliable point facility location problems on networks
- Location of alternative-fuel stations using the flow-refueling location model and dispersion of candidate sites on arcs
- Near-optimal dominating sets via random sampling
- Double bound method for solving the p-center location problem
- Eternal and Secure Domination in Graphs
- \((r|p)\)-centroid problems on networks with vertex and edge demand
- THE CONTINUOUS STOP LOCATION PROBLEM IN PUBLIC TRANSPORTATION NETWORKS
- scientific article; zbMATH DE number 1323024 (Why is no real title available?)
- Sequential competitive location on networks
- The collection depots location problem on networks
- scientific article; zbMATH DE number 1394671 (Why is no real title available?)
- Interpolating between \(k\)-median and \(k\)-center: approximation algorithms for ordered \(k\)-median
- More on the unimodality of domination polynomial of a graph
- J-means and I-means for minimum sum-of-squares clustering on networks
- The Domination Equivalence Classes of Paths
- On the structure of the solution set for the single facility location problem with average distances
- Multi-facility ordered median problems in directed networks
- Median problems in networks
- Discrete center problems
- The Location of Undesirable Facilities
- Exploiting Structure: Location Problems on Trees and Treelike Graphs
- The generalized p-centdian on network
- A fractional model for locating semi-desirable facilities on networks
- Approximability results for the $p$-centdian and the converse centdian problems
- An edge scanning method for the continuous deviation‐flow refueling station location problem on a general network
- Covering edges in networks
- Maximin and maxisum network location problems with various metrics and minimum distance constraints
- Finding the minimum k-weighted dominating sets using heuristic algorithms
- Balanced beneficiaries center of the graph
- On the exponential cardinality of FDS for the ordered p-median problem
- Multiple sink location problem in path networks with a combinational objective
- Minmax regret location--allocation problem on a network under uncertainty
This page was built for publication: Finite Dominating Sets for Network Location Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3981511)