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 (50)
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
This page was built for publication: Finding kth paths and p-centers by generating and searching good data structures
