Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
From MaRDI portal
Publication:3792728
DOI10.1137/0401038zbMath0648.05056OpenAlexW2073623633MaRDI QIDQ3792728
Publication date: 1988
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0401038
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph theory (05C99) Information storage and retrieval of data (68P20)
Related Items
Optimizing budget allocation for center and median points, On stabbing lines for convex polyhedra in 3D, A new bound and an \(O(mn)\) algorithm for the undesirable 1-median problem (maxian) on networks, Efficient algorithms for center problems in cactus networks, The connected \(p\)-center problem on cactus graphs, The \(w\)-centroids and least \(w\)-central subtrees in weighted trees, A quadratic time exact algorithm for continuous connected 2-facility location problem in trees, Efficient algorithms for centers and medians in interval and circular-arc graphs, On intersecting a set of parallel line segments with a convex polygon of minimum area, Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments, Undesirable facility location problems on multicriteria networks, Trees with unique least central subtrees, The general facility location problem with connectivity on trees, An \(O(mn)\) algorithm for the anti-cent-dian problem, An improved algorithm for the \(p\)-center problem on interval graphs with unit lengths, Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs, Approximability results for the $p$-centdian and the converse centdian problems, Approximability results for the converse connectedp-centre problem†, The Connected p-Center Problem on Cactus Graphs, The connected \(p\)-center problem on block graphs with forbidden vertices, The upper envelope of piecewise linear functions: Algorithms and applications, Maintaining centdians in a fully dynamic forest with top trees, On the minimum diameter spanning tree problem, Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs, The β-reliable minimax and maximin location problems on a network with probabilistic weights, Kinetic maintenance of mobile \(k\)-centres on trees, The weighted \(k\)-center problem in trees for fixed \(k\), One-way and round-trip center location problems, Homogeneous genetic algorithms, Discrete Center Problems, The Location of Undesirable Facilities, OPTIMAL FACILITY LOCATION UNDER VARIOUS DISTANCE FUNCTIONS, Center problems with pos/neg weights on trees
