A quadratic time exact algorithm for continuous connected 2-facility location problem in trees (Q1631680)

scientific article; zbMATH DE number 6990052

Language	Label	Description	Also known as
English	A quadratic time exact algorithm for continuous connected 2-facility location problem in trees	scientific article; zbMATH DE number 6990052

Statements

instance of

scholarly article

0 references

title

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees (English)

0 references

0 references

0 references

Journal of Combinatorial Optimization

0 references

publication date

6 December 2018

0 references

zbMATH Keywords

continuous connected 2-facility

0 references

tree

0 references

edge-splitting

0 references

quadratic time

0 references

MaRDI profile type

Publication

0 references

full work available at URL

https://doi.org/10.1007/s10878-017-0213-2

0 references

cites work

Proof verification and the hardness of approximation problems

0 references

An improved algorithm for the minmax regret median problem on a tree

0 references

Algorithms for the robust 1-center problem on a tree

0 references

Minimax regret p-center location on a network with demand uncertainty

0 references

Minmax Regret Median Location on a Network Under Uncertainty

0 references

The $p$-Center Problem in Tree Networks Revisited

0 references

Dual-based local search for the connected facility location and related problems

0 references

Algorithms for central-median paths with bounded length on trees

0 references

An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees

0 references

Mathematical Foundations of Computer Science 2003

0 references

Collection depots facility location problems in trees

0 references

The minimax multistop location problem on a tree

0 references

Optimal algorithms for the path/tree-shaped facility location problems in trees

0 references

A linear time algorithm for computing minmax regret 1-median on a tree network

0 references

Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks

0 references

An O$(n\log n)$ version of the Averbakh-Berman algorithm for the robust median of a tree

0 references

2-medians in trees with pos/neg weights

0 references

Center problems with pos/neg weights on trees

0 references

A note on the robust 1-center problem on trees

0 references

Robust location problems with pos/neg weights on a tree

0 references

The obnoxious center problem on a tree

0 references

A polynomial method for the pos/neg weighted 3-median problem on a tree

0 references

The $p$-maxian problem on a tree

0 references

Efficient algorithms for two generalized 2-median problems and the group median problem on trees

0 references

Polynomially bounded algorithms for locatingp-centers on a tree

0 references

An $O ( ( n\log p )^2 )$ Algorithm for the Continuous p-Center Problem on a Tree

0 references

Minmax-regret robust 1-median location on a tree

0 references

A note on the minmax regret centdian location on trees

0 references

A linear time algorithm for computing a most reliable source on a tree network with faulty nodes

0 references

On the 2-MRS problem in a tree with unreliable edges

0 references

Connected facility location via random facility sampling and core detouring

0 references

Distance-constrained multifacility minimax location problems on tree networks

0 references

Q4037428

0 references

Finding kth paths and p-centers by generating and searching good data structures

0 references

Q4198056

0 references

Provisioning a virtual private network

0 references

Simpler and better approximation algorithms for network design

0 references

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

0 references

Approximation algorithms for connected facility location problems

0 references

On locating path- or tree-shaped facilities on networks

0 references

Algorithms for finding P-centers on a weighted tree (for relatively small P)

0 references

Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem

0 references

An Algorithmic Approach to Network Location Problems. I: Thep-Centers

0 references

An Algorithmic Approach to Network Location Problems. II: Thep-Medians

0 references

Q5689811

0 references

Robust discrete optimization and its applications

0 references

Improved algorithms for some competitive location centroid problems on paths, trees and graphs

0 references

A Branch and Cut Algorithm for a Steiner Tree-Star Problem

0 references

New Results on the Complexity of p-Centre Problems

0 references

An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems

0 references

A single facility location problem on a tree with unreliable edges

0 references

The optimal location of a path or tree in a tree network

0 references

A linear algorithm for a core of a tree

0 references

Minimax regret path location on trees

0 references

The bi‐criteria doubly weighted center‐median path problem on a tree

0 references

Center location problems on tree graphs with subtree-shaped customers

0 references

Approximation Algorithms for Problems Combining Facility Location and Network Design

0 references

Primal-dual algorithms for connected facility location problems

0 references

An improved algorithm for the distance constrainedp-center location problem with mutual communication on tree networks

0 references

The $k$-centrum multi-facility location problem

0 references

Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem

0 references

An $O(pn^ 2)$ algorithm for the $p$-median and related problems on tree graphs

0 references

A unifying location model on tree graphs based on submodularity property

0 references

The least element property of center location on tree networks with applications to distance and precedence constrained problems

0 references

Obnoxious Facility Location on Graphs

0 references

Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures

0 references

The generalized P‐forest problem on a tree network

0 references

A polynomial algorithm for thep-centdian problem on a tree

0 references

Conditional location of path and tree shaped facilities on trees

0 references

The centdian subtree on tree networks

0 references

Locating Centers on a Tree with Discontinuous Supply and Demand Regions

0 references

Q4239707

0 references

Polyhedral properties of the $K$-median problem on a tree

0 references

Efficient Parallel Algorithms for Optimally Locating a Path and a Tree of a Specified Length in a Weighted Tree Network

0 references

An optimal algorithm for the weighted backup 2-center problem on a tree

0 references

Q4355484

0 references

On the minmax regret path median problem on trees

0 references

Improved algorithms for the minmax-regret 1-center and 1-median problems

0 references

An Edge-Turbulence Algorithm for the 2-MRS Problem on Trees with Unreliable Edges

0 references

Identifiers

zbMATH Open document ID

1412.90130

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

10.1007/S10878-017-0213-2

0 references

DBLP publication ID

journals/jco/DingQ18

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1631680