Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.11811 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914718624514048 |
|---|---|
| author | Sanim, Md. Musfiqur Rahman Saira, Safrunnesa Ahsan, Fatin Faiaz Bardhan, Rajon Ferdous, S. M. |
| author_facet | Sanim, Md. Musfiqur Rahman Saira, Safrunnesa Ahsan, Fatin Faiaz Bardhan, Rajon Ferdous, S. M. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_11811 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Simple 2-Approximation Algorithm For Minimum Manhattan Network Problem Sanim, Md. Musfiqur Rahman Saira, Safrunnesa Ahsan, Fatin Faiaz Bardhan, Rajon Ferdous, S. M. Computational Geometry Computer Science and Game Theory 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. |
| title | A Simple 2-Approximation Algorithm For Minimum Manhattan Network Problem |
| topic | Computational Geometry Computer Science and Game Theory |
| url | https://arxiv.org/abs/2403.11811 |