Computing the 2‐median on tree networks in O(n lg n) time

DOI10.1002/NET.3230260413MaRDI QIDQ4894868zbMATH OpenOpenAlexFDO

Authors Bezalel Gavish, Seshadri Sridhar

Publication date 13 November 1996

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230260413

zbMATH Keywords

tree networkslocation of facilities2-medians

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Communication networks in operations research (90B18) Discrete location and assignment (90B80)

Recommendations

• Erratum
• An O(pn^ 2) algorithm for the p-median and related problems on tree graphs
• Efficient computation of 2-medians in a tree network with positive/negative weights
• Efficient computation of 2-medians in a tree network with positive/negative weights
• scientific article; zbMATH DE number 2081038
• Efficient algorithms for finding <scp>2‐medians</scp> of a tree
• Efficient algorithms for two generalized 2-median problems and the group median problem on trees
• scientific article; zbMATH DE number 512926
• Algorithms – ESA 2005
• Mathematical Foundations of Computer Science 2003

Cited in

(28)

• Efficient algorithms for centers and medians in interval and circular-arc graphs
• Classical and inverse median location problems under uncertain environment
• The backup 2-median problem on block graphs
• The backup 2‐center and backup 2‐median problems on trees
• Finding an optimal core on a tree network with M/G/c/c state-dependent queues
• A combinatorial algorithm for the ordered 1-median problem on cactus graphs
• Optimal algorithms for selective variants of the classical and inverse median location problems on trees
• The balanced 2-median and 2-maxian problems on a tree
• Finding broadcast 2-centers of a tree under the postal model
• Inverse p-median problems with variable edge lengths
• 2-medians in trees with pos/neg weights
• Mean-variance value at risk criterion for solving a \(p\)-median location problem on networks with type-2 intuitionistic fuzzy weights
• The connected p-median problem on block graphs
• An algorithm for finding a k-median in a directed tree
• Efficient computation of 2-medians in a tree network with positive/negative weights
• Median problems with positive and negative weights on cycles and cacti
• Algorithms – ESA 2005
• A polynomial method for the pos/neg weighted 3-median problem on a tree
• The 2-radius and 2-radiian problems on trees
• A linear time algorithm for the \(p\)-maxian problem on trees with distance constraint
• The multi-service center problem
• Efficient algorithms for two generalized 2-median problems and the group median problem on trees
• Finding a core of a tree with pos/neg weight
• Efficient algorithms for finding <scp>2‐medians</scp> of a tree
• scientific article; zbMATH DE number 512926 (Why is no real title available?)
• On discrete preferences and coordination
• Median problems on wheels and cactus graphs
• scientific article; zbMATH DE number 7497034 (Why is no real title available?)

This page was built for publication: Computing the 2‐median on tree networks in O(n lg n) time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4894868)