English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Let B be a centrally symmetric convex polygon of R^2 and || p - q || be thedistance between two points p,q in R^2 in the normed plane whose unit ball isB. For a set T of n points (terminals) in R^2, a B-Manhattan network on T is anetwork N(T) = (V,E) with the property that its edges are parallel to thedirections of B and for every pair of terminals t_i and t_j, the network N(T)contains a shortest B-path between them, i.e., a path of length || t_i - t_j||. A minimum B-Manhattan network on T is a B-Manhattan network of minimumpossible length. The problem of finding minimum B-Manhattan networks has beenintroduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX'99) in the casewhen the unit ball B is a square (and hence the distance || p - q || is the l_1or the l_infty-distance between p and q) and it has been shown recently byChin, Guo, and Sun (SoCG'09) to be strongly NP-complete. Several approximationalgorithms (with factors 8, 4 ,3 , and 2) for minimum Manhattan problem areknown. In this paper, we propose a factor 2.5 approximation algorithm forminimum B-Manhattan network problem. The algorithm employs a simplified versionof the strip-staircase decomposition proposed in our paper (APPROX'05) andsubsequently used in other factor 2 approximation algorithms for minimumManhattan problem.

Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm