A Simple 2-Approximation for Maximum-Leaf Spanning Tree
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914736697769984 |
|---|---|
| author | Liao, I-Cheng Lu, Hsueh-I |
| author_facet | Liao, I-Cheng Lu, Hsueh-I |
| contents | For an $m$-edge connected simple graph $G$, finding a spanning tree of $G$ with the maximum number of leaves is MAXSNP-complete. The problem remains NP-complete even if $G$ is planar and the maximal degree of $G$ is at most four. Lu and Ravi gave the first known polynomial-time approximation algorithms with approximation factors $5$ and $3$. Later, they obtained a $3$-approximation algorithm that runs in near-linear time. The best known result is Solis-Oba, Bonsma, and Lowski's $O(m)$-time $2$-approximation algorithm. We show an alternative simple $O(m)$-time $2$-approximation algorithm whose analysis is simpler. This paper is dedicated to the cherished memory of our dear friend, Professor Takao Nishizeki. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_03125 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Simple 2-Approximation for Maximum-Leaf Spanning Tree Liao, I-Cheng Lu, Hsueh-I Data Structures and Algorithms 05C38, 05C10, 05C85, 68P05 For an $m$-edge connected simple graph $G$, finding a spanning tree of $G$ with the maximum number of leaves is MAXSNP-complete. The problem remains NP-complete even if $G$ is planar and the maximal degree of $G$ is at most four. Lu and Ravi gave the first known polynomial-time approximation algorithms with approximation factors $5$ and $3$. Later, they obtained a $3$-approximation algorithm that runs in near-linear time. The best known result is Solis-Oba, Bonsma, and Lowski's $O(m)$-time $2$-approximation algorithm. We show an alternative simple $O(m)$-time $2$-approximation algorithm whose analysis is simpler. This paper is dedicated to the cherished memory of our dear friend, Professor Takao Nishizeki. |
| title | A Simple 2-Approximation for Maximum-Leaf Spanning Tree |
| topic | Data Structures and Algorithms 05C38, 05C10, 05C85, 68P05 |
| url | https://arxiv.org/abs/2303.03125 |