Finding kth paths and p-centers by generating and searching good data structures
From MaRDI portal
Publication:4747524
DOI10.1016/0196-6774(83)90035-4zbMath0509.68057OpenAlexW1996896896MaRDI QIDQ4747524
Greg N. Frederickson, Donald B. Johnson
Publication date: 1983
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(83)90035-4
path selectionp-center locationnetworks with independent cyclesrepresentation of the set of intervertex distances of a tree
Trees (05C05) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Algorithms in computer science (68W99)
Related Items
Bounded fan-out \(m\)-center problem, Efficient algorithms for center problems in cactus networks, A quadratic time exact algorithm for continuous connected 2-facility location problem in trees, Improved algorithms for some competitive location centroid problems on paths, trees and graphs, Improvements on geometric pattern matching problems, A finite algorithm for the continuousp-center location problem on a graph, Reverse shortest path problem in weighted unit-disk graphs, Polynomial algorithms for restricted Euclidean p-centre problems, Network construction/restoration problems: cycles and complexity, Extensive facility location problems on networks: an updated review, Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs, A tight bound on the min-ratio edge-partitioning problem of a tree, A centroid labelling technique and its application to path selection in trees, Getting around a lower bound for the minimum Hausdorff distance, Geometric pattern matching in d-dimensional space, Geometric p-Center Problems with Centers Constrained to Two Lines, A linear-time algorithm for finding an edge-partition with max-min ratio at most two, The Approximability of Partial Vertex Covers in Trees, Backup 2-center on interval graphs, Sorting weighted distances with applications to objective function evaluations in single facility location problems., Finding the conditional location of a median path on a tree, Enumerations, forbidden subgraph characterizations, and the split-decomposition, Efficient algorithms for the one-dimensional \(k\)-center problem, Optimizing squares covering a set of points, Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence, Exploration of \(k\)-edge-deficient temporal graphs, A simple linear algorithm for computing rectilinear 3-centers, Range minimization problems in path-facility location on trees, The backup 2‐center and backup 2‐median problems on trees, An improved algorithm for diameter-optimally augmenting paths in a metric space, On some geometric selection and optimization problems via sorted matrices, 3-PIERCING OF d-DIMENSIONAL BOXES AND HOMOTHETIC TRIANGLES, Minsum \(k\)-sink problem on path networks, Center location problems on tree graphs with subtree-shaped customers, Unnamed Item, Unnamed Item, Efficient parallel algorithms for r-dominating set and p-center problems on trees, Locating an absolute center on graphs that are almost trees, On some geometric selection and optimization problems via sorted matrices, Covering uncertain points in a tree, Optimal algorithms for the path/tree-shaped facility location problems in trees, Continuous bottleneck tree partitioning problems, Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points, An O(n log n)-Time Algorithm for the k-Center Problem in Trees, Discrete Center Problems, Exploiting Structure: Location Problems on Trees and Treelike Graphs, An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees, Modeling uncertainty in networks, Locating two obnoxious facilities using the weighted maximin criterion, The centdian subtree on tree networks