A linear-time algorithm for solving the center problem on weighted cactus graphs

DOI10.1016/S0020-0190(99)00111-8MaRDI QIDQ1606995zbMATH OpenOpenAlexWikidataFDO

Authors Yu-Feng Lan, Yue-Li Wang, Hitoshi Suzuki

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

zbMATH Keywords

centerdistanceeccentricityoptimal algorithmradiusweighted cactus graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The obnoxious center problem on weighted cactus graphs.
• Algorithms and Computation
• scientific article; zbMATH DE number 1786156
• scientific article; zbMATH DE number 2166874
• Efficient algorithms for center problems in cactus networks

Cites work

• An optimal parallel algorithm for computing furthest neighbors in a tree
• Block-vertex duality and the one-median problem
• Depth-First Search and Linear Graph Algorithms
• Distributed algorithms for finding centers and medians in networks
• scientific article; zbMATH DE number 3847184 (Why is no real title available?)
• scientific article; zbMATH DE number 3666528 (Why is no real title available?)
• scientific article; zbMATH DE number 44281 (Why is no real title available?)
• Locating an absolute center on graphs that are almost trees
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
• Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
• State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure

Cited in

(19)

• The obnoxious center problem on weighted cactus graphs.
• An optimal algorithm for solving the 1-median problem on weighted 4-cactus graphs
• Center problems with pos/neg weights on trees
• A linear time algorithm for weighted \(k\)-fair domination problem in cactus graphs
• Augmenting a tree to a k-arbor-connected graph with pagenumber k
• Efficient algorithms for center problems in cactus networks
• scientific article; zbMATH DE number 4173027 (Why is no real title available?)
• The connected p-center problem on block graphs with forbidden vertices
• Backup 2-center on interval graphs
• scientific article; zbMATH DE number 2166874 (Why is no real title available?)
• The backup 2‐center and backup 2‐median problems on trees
• Algorithms and Computation
• Computation of diameter, radius and center of permutation graphs
• Computing the center of uncertain points on cactus graphs
• A linear-time algorithm for the center problem in weighted cycle graphs
• Computing the center of uncertain points on cactus graphs
• The connected k-vertex one-center problem on graphs
• Eccentricity function in distance-hereditary graphs
• The 2-radius and 2-radiian problems on trees

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: A linear-time algorithm for solving the center problem on weighted cactus graphs

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