Efficient algorithms for center problems in cactus networks

DOI10.1016/j.tcs.2007.02.033zbMath1120.68109MaRDI QIDQ2371802

Binay K. Bhattacharya, Arie Tamir, Boaz Ben-Moshe, Qiaosheng Shi

Publication date: 9 July 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.033

zbMATH Keywords

cactus networks; center problems; facility location optimization

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

90B80: Discrete location and assignment

Related Items

The connected \(p\)-center problem on block graphs with forbidden vertices, Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks, Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs

Cites Work

• Unnamed Item
• Fractional cascading. I: A data structuring technique
• Fractional cascading. II: Applications
• On search over rationals
• A \(p\)-center grid-positioning aggregation procedure
• On some optimization problems on \(k\)-trees and partial \(k\)-trees
• Parallel concepts in graph theory
• A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
• The obnoxious center problem on weighted cactus graphs.
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• A linear-time algorithm for solving the center problem on weighted cactus graphs
• Center problems with pos/neg weights on trees
• The Obnoxious Center Problem on a Tree
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• New Results on the Complexity of p-Centre Problems
• Algorithms for finding P-centers on a weighted tree (for relatively small P)
• Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
• Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
• The 1-Center Problem: Exploiting Block Structure
• Off-Line Maintenance of Planar Configurations
• Combinatorial Optimization with Rational Objective Functions
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• Obnoxious Facility Location on Graphs
• Slowing down sorting networks to obtain faster sorting algorithms
• Finding kth paths and p-centers by generating and searching good data structures
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth