A Simple 2-Approximation Algorithm For Minimum Manhattan Network Problem
<|reference_start|>A Simple 2-Approximation Algorithm For Minimum Manhattan Network Problem: Given a n 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 two point in G should be connected by a Manhattan path and distance between this two points is equal to Manhattan Distance. The Minimum Manhattan Network problem is to find a Manhattan network with minimum network length, i.e., summation of all line segment in network should be minimize. In this paper, we proposed a 2-approximation algorithm with time complexity O(|E|lgN) where |E| is the number of edges and N is the number of nodes. Using randomly generated datasets, we compare our result with the optimal one.<|reference_end|>
@article{sanim2024a,
    title={A Simple 2-Approximation Algorithm For Minimum Manhattan Network Problem},
    author={Md. Musfiqur Rahman Sanim, Safrunnesa Saira, Fatin Faiaz Ahsan, Rajon
  Bardhan, S.M. Ferdous},
    journal={arXiv preprint arXiv:2403.11811},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.11811},
    primaryClass={cs.CG cs.GT}
}