Median problems on wheels and cactus graphs

DOI10.1007/s00607-007-0238-yzbMath1170.90467OpenAlexW2088391504MaRDI QIDQ2457944

Johannes Hatzl

Publication date: 24 October 2007

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00607-007-0238-y

zbMATH Keywords

location problemcactus graphsmedian problemwheel graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27)

Related Items

The connected \(p\)-median problem on block graphs, The shortest connection game, The backup 2-median problem on block graphs, Partition distance in graphs, Optimal algorithms for selective variants of the classical and inverse median location problems on trees, Exploiting Structure: Location Problems on Trees and Treelike Graphs

Cites Work

• Unnamed Item
• Median problems with positive and negative weights on cycles and cacti
• A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• Block-vertex duality and the one-median problem
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Computing the 2‐median on tree networks in O(n lg n) time
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph