Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane
H Cambazard, N Catusse - European Journal of Operational Research, 2018 - Elsevier
Given a set P of n points with their pairwise distances, the traveling salesman problem (TSP)
asks for a shortest tour that visits each point exactly once. A TSP instance is rectilinear when …
asks for a shortest tour that visits each point exactly once. A TSP instance is rectilinear when …
Minimum Manhattan network is NP-complete
A rectilinear path between two points p, q∈ R2 is a path connecting p and q with all its line
segments horizontal or vertical segments. Furthermore, a Manhattan path between p and q …
segments horizontal or vertical segments. Furthermore, a Manhattan path between p and q …
A Simple 2-Approximation Algorithm For Minimum Manhattan Network Problem
MMR Sanim, S Saira, FF Ahsan, R Bardhan… - arXiv preprint arXiv …, 2024 - arxiv.org
Given an points in two dimensional space, a Manhattan Network G is a network that
connects all n points with either horizontal or vertical edges, with the property that for any …
connects all n points with either horizontal or vertical edges, with the property that for any …
Greedy construction of 2-approximation minimum Manhattan network
Given a set T of n points in, a Manhattan Network G is a network with all its edges horizontal
or vertical segments, such that for all p, q∈ T, in G there exists a path (named a Manhattan …
or vertical segments, such that for all p, q∈ T, in G there exists a path (named a Manhattan …
Greedy construction of 2-approximate minimum Manhattan networks
Given a set T of n points in ℝ2, a Manhattan network on T is a graph G=(V, E) with the
property that all the edges in E are vertical or horizontal line segments connecting points in …
property that all the edges in E are vertical or horizontal line segments connecting points in …
A fixed-parameter algorithm for the minimum Manhattan network problem
C Knauer, A Spillner - Journal of Computational Geometry, 2011 - jocg.org
A Manhattan network for a finite set P of points in the plane is a geometric graph such that its
vertex set contains P, its edges are axis-parallel and non-crossing and, for any two points p …
vertex set contains P, its edges are axis-parallel and non-crossing and, for any two points p …
[HTML][HTML] Searching for realizations of finite metric spaces in tight spans
S Herrmann, V Moulton, A Spillner - Discrete Optimization, 2013 - Elsevier
An important problem that commonly arises in areas such as internet traffic-flow analysis,
phylogenetics and electrical circuit design, is to find a representation of any given metric D …
phylogenetics and electrical circuit design, is to find a representation of any given metric D …
On Minimum Generalized Manhattan Connections
A Antoniadis, M Capretto, P Chalermsook… - Algorithms and Data …, 2021 - Springer
We consider minimum-cardinality Manhattan connected sets with arbitrary demands: Given
a collection of points P in the plane, together with a subset of pairs of points in P (which we …
a collection of points P in the plane, together with a subset of pairs of points in P (which we …
[PDF][PDF] A Simulated Annealing approach for solving Minimum Manhattan Network Problem
SM Ferdous, A Das - International Journal of Computer Applications, 2014 - Citeseer
In this paper we address the Minimum Manhattan Network (MMN) problem. It is an important
geometric problem with vast applications. As it is an NP-complete discrete combinatorial …
geometric problem with vast applications. As it is an NP-complete discrete combinatorial …
Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm
N Catusse, V Chepoi, K Nouioua, Y Vaxes - Algorithmica, 2012 - Springer
Let B be a centrally symmetric convex polygon of ℝ 2 and‖ p− q‖ be the distance between
two points p, q∈ ℝ 2 in the normed plane whose unit ball is B. For a set T of n points …
two points p, q∈ ℝ 2 in the normed plane whose unit ball is B. For a set T of n points …