Polynomially bounded algorithms for locatingp-centers on a tree

DOI10.1007/BF01581045zbMATH Open0486.90036MaRDI QIDQ3947422FDOQ3947422

Authors: 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)

Cites Work

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

Cited In (22)

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

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

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