Approximately covering vertices by order-$5$ or longer paths
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916363518345216 |
|---|---|
| author | Gong, Mingyang Chen, Zhi-Zhong Lin, Guohui Wang, Lusheng |
| author_facet | Gong, Mingyang Chen, Zhi-Zhong Lin, Guohui Wang, Lusheng |
| contents | This paper studies $MPC^{5+}_v$, which is to cover as many vertices as possible in a given graph $G=(V,E)$ by vertex-disjoint $5^+$-paths (i.e., paths each with at least five vertices). $MPC^{5+}_v$ is NP-hard and admits an existing local-search-based approximation algorithm which achieves a ratio of $\frac {19}7\approx 2.714$ and runs in $O(|V|^6)$ time. In this paper, we present a new approximation algorithm for $MPC^{5+}_v$ which achieves a ratio of $2.511$ and runs in $O(|V|^{2.5} |E|^2)$ time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_11225 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximately covering vertices by order-$5$ or longer paths Gong, Mingyang Chen, Zhi-Zhong Lin, Guohui Wang, Lusheng Data Structures and Algorithms Discrete Mathematics This paper studies $MPC^{5+}_v$, which is to cover as many vertices as possible in a given graph $G=(V,E)$ by vertex-disjoint $5^+$-paths (i.e., paths each with at least five vertices). $MPC^{5+}_v$ is NP-hard and admits an existing local-search-based approximation algorithm which achieves a ratio of $\frac {19}7\approx 2.714$ and runs in $O(|V|^6)$ time. In this paper, we present a new approximation algorithm for $MPC^{5+}_v$ which achieves a ratio of $2.511$ and runs in $O(|V|^{2.5} |E|^2)$ time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion. |
| title | Approximately covering vertices by order-$5$ or longer paths |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2408.11225 |