New Results on the Complexity of p-Center Problems

No abstract is available for this paper.

• Publication year

  1983

• Venue

  SIAM journal on computing (Print)

• Publication date

  1983-11-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/0212051
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Finding k-th Paths and p-Centers by Generating and Searching Good Data Structures

  1983cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• Applying parallel computation algorithms in the design of serial algorithms

  1981cited by this paper
• Location on Tree Networks: P-Centre and n-Dispersion Problems

  1981cited by this paper
• An O(n log2 n) Algorithm for the k-th Longest Path in a Tree with Applications to Location Problems

  1981influential reference
• Generating and Searching Sets Induced by Networks

  1980cited by this paper
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper
• Finding Two-Centers of a Tree: The Continuous Case

  1978cited by this paper
• New Parallel-Sorting Schemes

  1978cited by this paper
• Parallelism in Comparison Problems

  1975cited by this paper
• The Design and Analysis of Computer Algorithms

  1974cited by this paper
• Minimax Location of a Facility in an Undirected Tree Graph

  1973cited by this paper

• Faster Approximation Algorithms for k-Center via Data Reduction

  2025cites this paper
• Improved algorithms for optimal k sink location on path networks

  2025cites this paper
• Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances

  2025cites this paper
• Combinatorial properties of continuous graphs: A survey of challenges, solutions and open problems

  2025cites this paper
• The k-Center Problem of Uncertain Points on Graphs

  2025cites this paper
• Beyond location modeling and GIS: Integration and bridging

  2025cites this paper
• Approximating δ-Covering

  2024cites this paper
• From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $\delta$-Covering All Points on All Edges

  2024cites this paper
• From Chinese Postman to Salesman and Beyond: Shortest Tour δ-Covering All Points on All Edges

  2024cites this paper
• The <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e101" altimg="si185.svg"><mml:mi>p</mml:mi></mml:math>-center problem under locational uncertainty of demand points

  2023cites this paper
• A Weighted K-Center Algorithm for Data Subset Selection

  2023cites this paper
• New approaches to the robust 1-center location problems on tree networks

  2022cites this paper
• An Equity-Based Optimization Model to Solve the Location Problem for Healthcare Centers Applied to Hospital Beds and COVID-19 Vaccination

  2022cites this paper
• The Weighted k-Center Problem in Trees for Fixed k

  2022cites this paper
• The Coverage Problem by Aligned Disks

  2022cites this paper
• Improvements on approximation algorithms for clustering probabilistic data

  2021cites this paper
• Unified Polynomial Dynamic Programming Algorithms for P-Center Variants in a 2D Pareto Front

  2021cites this paper
• Clustering a 2d Pareto Front: P-center Problems Are Solvable in Polynomial Time

  2020influential citation
• Polynomial algorithms for p-dispersion problems in a planar Pareto Front

  2020cites this paper
• Approximation algorithms for probabilistic $k$-center clustering

  2020cites this paper
• k-medoids and p-median clustering are solvable in polynomial time for a 2d Pareto front.

  2020cites this paper
• Integer Programming and Combinatorial Optimization: 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings

  2020cites this paper
• Continuous facility location on graphs

  2020cites this paper
• Solution methods for a min–max facility location problem with regional customers considering closest Euclidean distances

  2020cites this paper
• A Linear-Time Algorithm for Radius-Optimally Augmenting Paths in a Metric Space

  2019cites this paper
• Planar p-center problems are solvable in polynomial time when clustering a Pareto Front

  2019influential citation
• Classical Center Location Problem Under Uncertain Environment

  2019cites this paper
• Exact algorithms for handling outliers in center location problems on networks using k-max functions

  2019cites this paper
• Uniform and most uniform partitions of trees

  2018cites this paper
• Minmax Centered k-Partitioning of Trees and Applications to Sink Evacuation with Dynamic Confluent Flows

  2018cites this paper
• Improved constant approximation factor algorithms for k-center problem for uncertain data

  2018cites this paper
• Clustering in a 2d Pareto Front: p-median and p-center are solvable in polynomial time

  2018cites this paper
• On the Coverage of Points in the Plane by Disks Centered at a Line

  2018cites this paper
• Clustering in a 2-dimensional Pareto Front: the p-median and p-center problems are polynomially solvable

  2018cites this paper
• Dispersing Obnoxious Facilities on a Graph

  2018cites this paper
• Improved Algorithms for Computing k-Sink on Dynamic Flow Path Networks

  2017cites this paper
• An O(n\log n)-Time Algorithm for the k-Center Problem in Trees

  2017influential citation
• A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

  2017cites this paper
• Dispersion on Trees

  2017cites this paper
• Covering Uncertain Points in a Tree

  2017influential citation
• Geometric Facility Location Problems on Uncertain Data

  2017influential citation
• Throttling for the game of Cops and Robbers on graphs

  2017influential citation
• On Two Problems Regarding Farthest Distances in Continuous Networks

  2017cites this paper
• Algorithms for weighted coloring problems

  2017cites this paper
• Improvements on the k-center Problem for Uncertain Data

  2017cites this paper
• A note on computing the center of uncertain data on the real line

  2016cites this paper
• The $p$-Center Problem in Tree Networks Revisited

  2016influential citation
• Algorithms for uniform centered partitions of trees

  2016cites this paper
• Slowing down sorting networks to obtain faster sorting algorithms

  2015cites this paper
• Geometric k-Center Problems with Centers Constrained to Two Lines

  2015cites this paper
• Computing the Center of Uncertain Points on Tree Networks

  2015cites this paper
• Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks

  2015cites this paper
• Scalable Algorithms for Large and Dynamic Networks: Reducing Big Data for Small Computations

  2015cites this paper
• Efficient algorithms for the one-dimensional k-center problem

  2015cites this paper
• One-dimensional k-center on uncertain data

  2015cites this paper
• Complexity of fuzzy answer set programming under Łukasiewicz semantics

  2014influential citation
• One-Dimensional k-Center on Uncertain Data

  2014cites this paper
• Scheduling with gaps: new models and algorithms

  2014cites this paper
• Improved algorithms to network p-center location problems

  2014cites this paper
• Improved Minmax Regret 1-Center Algorithms for Cactus Networks with c Cycles

  2014cites this paper
• Efficient Algorithms for One-Dimensional k-Center Problems

  2013cites this paper
• Double bound method for solving the p-center location problem

  2013cites this paper
• Exact solution Methodologies for the P-Center Problem under single and Multiple Allocation Strategies

  2013cites this paper
• Backup 2-center on interval graphs

  2012cites this paper
• Experimental approaches to computational geometric and statistical machine translation problems

  2012cites this paper
• On Covering Points with Conics and Strips in the Plane

  2012cites this paper
• Improved complexity results for several multifacility location problems on trees

  2011cites this paper
• Instant approximate 1-center on road networks via embeddings

  2011cites this paper
• Discrete Center Problems

  2011cites this paper
• Efficient Algorithms for the Weighted k-Center Problem on a Real Line

  2011cites this paper
• Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches

  2010cites this paper
• Obstacle Constrained Total Area Coverage in Wireless Sensor Networks

  2010cites this paper
• The backup 2‐center and backup 2‐median problems on trees

  2009cites this paper
• The backup 2-center and backup 2-median problems on trees

  2009cites this paper
• Locating Facilities Th at Serve Cycles, Not Nodes

  2009cites this paper
• Finding the conditional location of a median path on a tree

  2008cites this paper
• Routing for Relief Efforts

  2008cites this paper
• Price competition with elastic traffic

  2008cites this paper
• Towards a mission planning toolbox for the Airborne Network: Optimizing ground coverage under connectivity constraints

  2008cites this paper
• Application of computational geometry to network p-center location problems

  2008cites this paper
• Efficient algorithms for network center/covering location optimization problems

  2008cites this paper
• Network search games, with arbitrary searcher starting point

  2008cites this paper
• Center location problems on tree graphs with subtree-shaped customers

  2008influential citation
• Network search games with immobile hider, without a designated searcher starting point

  2008cites this paper
• Hide‐and‐seek games on a tree to which Eulerian networks are attached

  2008cites this paper
• Optimal Algorithms for the Weighted p -Center Problems on the Real Line for Small p

  2007cites this paper
• Efficient algorithms for center problems in cactus networks

  2007cites this paper
• Locating Facilities on a Network to Minimize Their Average Service Radius

  2007cites this paper
• A linear time algorithm for the backup 2-center problem on a tree

  2007cites this paper
• Competitive Algorithms for Maintaining a Mobile Center

  2006cites this paper
• Minmax regret 1-center problem on a network with a discrete set of scenarios

  2006cites this paper
• An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees

  2006influential citation
• Locating two obnoxious facilities using the weighted maximin criterion

  2006cites this paper
• Genetic algorithm to solve the p-centre and p-radius problem on a network

  2005cites this paper
• Efficient Algorithms for the Weighted 2-Center Problem in a Cactus Graph

  2005cites this paper
• VERY SHORT COURSE ON LP

  2005cites this paper
• One-way and round-trip center location problems

  2005cites this paper
• Continuous bottleneck tree partitioning problems

  2004influential citation
• An improved algorithm for the distance constrained p‐center location problem with mutual communication on tree networks

  2004cites this paper
• Finding r-dominating sets and p-centers of trees in parallel

  2004cites this paper