Polynomially bounded algorithms for locatingp-centers on a tree

DOI10.1007/BF01581045zbMath0486.90036MaRDI QIDQ3947422

R. Chandrasekaran, Arie Tamir

Publication date: 1982

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmperfect graphslocation on a treeundirected tree networkdual location modelp-center location problemrigid circuit graphs

Mathematics Subject Classification ID

Inventory, storage, reservoirs (90B05)

Related Items (21)

Perfect edge domination and efficient edge domination in graphs ⋮ A quadratic time exact algorithm for continuous connected 2-facility location problem in trees ⋮ New linear time algorithms for generating perfect elimination orderings of chordal graphs ⋮ Analytical models for locating undesirable facilities ⋮ A Class of Balanced Matrices Arising from Location Problems ⋮ Dually chordal graphs ⋮ On domination elimination orderings and domination graphs ⋮ Bee colony optimization for the \(p\)-center problem ⋮ The discrete p-dispersion problem ⋮ Locational analysis ⋮ Some aspects of the semi-perfect elimination ⋮ The 1-center problem in the plane with independent random weights ⋮ One-dimensional \(k\)-center on uncertain data ⋮ Efficient algorithms for the one-dimensional \(k\)-center problem ⋮ A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs ⋮ A note on computing the center of uncertain data on the real line ⋮ Efficient parallel algorithms for r-dominating set and p-center problems on trees ⋮ Dominant, an algorithm for the \(p\)-center problem. ⋮ An O(n log n)-Time Algorithm for the k-Center Problem in Trees ⋮ Some aspects of perfect elimination orderings in chordal graphs ⋮ An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees

Cites Work

• On rigid circuit graphs
• Time bounds for selection
• A characterisation of rigid circuit graphs
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• Location on Tree Networks: P-Centre and n-Dispersion Problems
• Algorithmic Aspects of Vertex Elimination on Graphs
• Perfect zero–one matrices
• The m-Center Problem
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Blocking and anti-blocking pairs of polyhedra
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph

This page was built for publication: Polynomially bounded algorithms for locatingp-centers on a tree