An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
From MaRDI portal
Publication:3906433
DOI10.1137/0210023zbMath0456.68071OpenAlexW2141178123MaRDI QIDQ3906433
Nimrod Megiddo, Arie Tamir, R. Chandrasekaran, Eitan Zemel
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210023
Related Items
An efficient algorithm for the length-constrained heaviest path problem on a tree, 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, A finite algorithm for the continuousp-center location problem on a graph, The Kth TSP is pseudopolynomial when TSP is polynomial, Double bound method for solving the \(p\)-center location problem, Polynomial algorithms for restricted Euclidean p-centre problems, Polyhedral properties of the \(K\)-median problem on a tree, Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Optimal algorithms for generalized searching in sorted matrices, A centroid labelling technique and its application to path selection in trees, A Class of Balanced Matrices Arising from Location Problems, Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows, The connected \(p\)-center problem on block graphs with forbidden vertices, The two-center problem of uncertain points on a real line, The \(p\)-center problem under locational uncertainty of demand points, Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms, Improved algorithms for several network location problems with equality measures., Backup 2-center on interval graphs, 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, Finding the conditional location of a median path on a tree, One-dimensional \(k\)-center on uncertain data, Efficient algorithms for the one-dimensional \(k\)-center problem, Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence, The 2-radius and 2-radiian problems on trees, Computing the center of uncertain points on tree networks, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Complexity issues in vertex-colored graph pattern matching, Range minimization problems in path-facility location on trees, A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters, Center location problems on tree graphs with subtree-shaped customers, Unnamed Item, Efficient parallel algorithms for r-dominating set and p-center problems on trees, Covering uncertain points in a tree, K-center and K-median problems in graded distances, Optimal algorithms for the path/tree-shaped facility location problems in trees, Partial and perfect path covers of cographs, One-way and round-trip center location problems, An O(n log n)-Time Algorithm for the k-Center Problem in Trees, Discrete Center Problems, An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees, The centdian subtree on tree networks, Algorithmic results for ordered median problems, Center problems with pos/neg weights on trees
