An Algorithmic Approach to Network Location Problems. I: Thep-Centers

DOI10.1137/0137040zbMath0432.90074OpenAlexW4239852074WikidataQ59760353 ScholiaQ59760353MaRDI QIDQ3870690

S. Louis Hakimi, Oded Kariv

Publication date: 1979

Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0137040

zbMATH Keywords

treecomputational complexitygraphNP-complete problemspolynomial algorithmdominating setcentersnetwork locationcentroidmediansdiameter of graphservicingmin-max criterionlocation of service stationp-centersw-centroid

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Queues and service in operations research (90B22) Applications of graph theory to circuits and networks (94C15)

Related Items (only showing first 100 items - show all)

Efficient algorithms for the round-trip 1-center and 1-median problems ⋮ Exact algorithms for handling outliers in center location problems on networks using \(k\)-max functions ⋮ Inverse 1-median problem on block graphs with variable vertex weights ⋮ A linear time algorithm for the \(p\)-maxian problem on trees with distance constraint ⋮ Bounded fan-out \(m\)-center problem ⋮ The \(p\)-neighbor \(k\)-center problem ⋮ Finding a longest nonnegative path in a constant degree tree ⋮ An efficient algorithm for the length-constrained heaviest path problem on a tree ⋮ The mixed center location problem ⋮ A quadratic time exact algorithm for continuous connected 2-facility location problem in trees ⋮ Kinetic clustering of points on the line ⋮ Inverse eccentric vertex problem on networks ⋮ A scalable exact algorithm for the vertex \(p\)-center problem ⋮ The linking set problem: a polynomial special case of the multiple-choice knapsack problem ⋮ Finding the \(\ell\)-core of a tree ⋮ A heuristic for the p-center problem in graphs ⋮ Capacitated \(p\)-center problem with failure foresight ⋮ The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance ⋮ Continuous multifacility ordered median location problems ⋮ Maximum weight independent set in trees ⋮ Robust vertex \(p\)-center model for locating urgent relief distribution centers ⋮ Double bound method for solving the \(p\)-center location problem ⋮ Improving the quality of heuristic solutions for the capacitated vertex \(p\)-center problem through iterated greedy local search with variable neighborhood descent ⋮ When centers can fail: a close second opportunity ⋮ Representation of the non-dominated set in biobjective discrete optimization ⋮ An \(O(mn)\) algorithm for the anti-cent-dian problem ⋮ An improved algorithm for the \(p\)-center problem on interval graphs with unit lengths ⋮ Location and layout planning. A survey ⋮ An improved algorithm for the minmax regret path centdian problem on trees ⋮ The biobjective absolute center problem ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs ⋮ The multi-service center problem ⋮ Designing humanitarian supply chains by incorporating actual post-disaster decisions ⋮ Bounded-degree minimum-radius spanning trees in wireless sensor networks ⋮ A double annealing algorithm for discrete location/allocation problems ⋮ The probabilistic \(p\)-center problem: planning service for potential customers ⋮ Two paths location of a tree with positive or negative weights ⋮ The connected \(p\)-center problem on block graphs with forbidden vertices ⋮ NP-completeness of some type of p-center problem ⋮ Progressive scattered data filtering. ⋮ The absolute center of a unicyclic network ⋮ Backup 2-center on interval graphs ⋮ The discrete p-dispersion problem ⋮ Algorithms for the m-center problems: A survey ⋮ The distance-domination numbers of trees ⋮ Synthetic optimization model and algorithm for railway freight center station location and wagon flow organization problem ⋮ Sorting weighted distances with applications to objective function evaluations in single facility location problems. ⋮ On search over rationals ⋮ On locating new facilities in a competitive environment ⋮ Locational analysis ⋮ The inverse 1-center problem on cycles with variable edge lengths ⋮ An algorithm to evaluate public transportation stops for minimizing passenger walking distance ⋮ An algorithm for finding the absolute center of a network ⋮ The maximin gradual cover location problem ⋮ Location routing problems on trees ⋮ Algorithms for the minimum diameter terminal Steiner tree problem ⋮ Total distance, Wiener index and opportunity index in wreath products of star graphs ⋮ Inverse \(k\)-centrum problem on trees with variable vertex weights ⋮ On the minimum diameter spanning tree problem ⋮ Efficient algorithms for the one-dimensional \(k\)-center problem ⋮ Computing the clique-width of cactus graphs ⋮ Sequential location of two facilities: comparing random to optimal location of the first facility ⋮ An optimal algorithm for the weighted backup 2-center problem on a tree ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ Combinatorial network abstraction by trees and distances ⋮ The 2-radius and 2-radiian problems on trees ⋮ A reactive GRASP for a commercial territory design problem with multiple balancing requirements ⋮ New relaxation-based algorithms for the optimal solution of the continuous and discrete \(p\)-center problems ⋮ On worst-case aggregation analysis for network location problems ⋮ Network location of a reliable center using the most reliable route policy ⋮ The minimum weight \(t\)-composition of an integer ⋮ Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms ⋮ Star \(p\)-hub center problem and star \(p\)-hub median problem with bounded path lengths ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ Orthogonal segment stabbing ⋮ Approximation algorithm for the kinetic robust \(k\)-center problem ⋮ Location analysis: a synthesis and survey ⋮ Group centre and group median of a tree ⋮ Efficient parallel algorithms for r-dominating set and p-center problems on trees ⋮ Locating an absolute center on graphs that are almost trees ⋮ Dominant, an algorithm for the \(p\)-center problem. ⋮ On weighted rectilinear 2-center and 3-center problems ⋮ Approximate maxima finding of continuous functions under restricted budget ⋮ Aggregation error for location models: Survey and analysis ⋮ A simple heuristic for the p-centre problem ⋮ Kinetic maintenance of mobile \(k\)-centres on trees ⋮ Improved complexity results for several multifacility location problems on trees ⋮ Generalized \(p\)-center problems: Complexity results and approximation algorithms ⋮ Improved approximability and non-approximability results for graph diameter decreasing problems ⋮ Algorithms for the robust 1-center problem on a tree ⋮ Vertex fusion under distance constraints ⋮ Some new algorithms for location problems on networks ⋮ The absolute centre of a graph ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Network location problems with continuous link demands: p-medians on a chain and 2-medians on a tree ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ The least element property of center location on tree networks with applications to distance and precedence constrained problems ⋮ Enhancements to two exact algorithms for solving the vertex \(P\)-center problem ⋮ Demand point aggregation for planar covering location models

This page was built for publication: An Algorithmic Approach to Network Location Problems. I: Thep-Centers