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

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