A linear-time algorithm for solving the center problem on weighted cactus graphs
From MaRDI portal
Publication:1606995
DOI10.1016/S0020-0190(99)00111-8zbMath0995.05134OpenAlexW2009881909WikidataQ127451164 ScholiaQ127451164MaRDI QIDQ1606995
Hitoshi Suzuki, Yue-Li Wang, Yu-Feng Lan
Publication date: 25 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(99)00111-8
Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (10)
Efficient algorithms for center problems in cactus networks ⋮ Computation of diameter, radius and center of permutation graphs ⋮ The connected \(p\)-center problem on block graphs with forbidden vertices ⋮ Computing the center of uncertain points on cactus graphs ⋮ Backup 2-center on interval graphs ⋮ The obnoxious center problem on weighted cactus graphs. ⋮ The 2-radius and 2-radiian problems on trees ⋮ The backup 2‐center and backup 2‐median problems on trees ⋮ Augmenting a tree to a \(k\)-arbor-connected graph with pagenumber \(k\) ⋮ Center problems with pos/neg weights on trees
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An optimal parallel algorithm for computing furthest neighbors in a tree
- Locating an absolute center on graphs that are almost trees
- Distributed algorithms for finding centers and medians in networks
- State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
- Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
- Block-vertex duality and the one-median problem
- Depth-First Search and Linear Graph Algorithms
- Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
This page was built for publication: A linear-time algorithm for solving the center problem on weighted cactus graphs
