A Parameterized Perspective on $P_2$-Packings
| dc.creator | Chen, Jianer | |
| dc.creator | Fernau, Henning | |
| dc.creator | Ning, Dan | |
| dc.creator | Raible, Daniel | |
| dc.creator | Wang, Jianxin | |
| dc.date | 2008-04-03 | |
| dc.date.accessioned | 2026-07-07T12:18:05Z | |
| dc.date.available | 2026-07-07T12:18:05Z | |
| dc.description | }We study (vertex-disjoint) $P_2$-packings in graphs under a parameterized perspective. Starting from a maximal $P_2$-packing $\p$ of size $j$ we use extremal arguments for determining how many vertices of $\p$ appear in some $P_2$-packing of size $(j+1)$. We basically can 'reuse' $2.5j$ vertices. We also present a kernelization algorithm that gives a kernel of size bounded by $7k$. With these two results we build an algorithm which constructs a $P_2$-packing of size $k$ in time $\Oh^*(2.482^{3k})$. | |
| dc.identifier | https://arxiv.org/abs/0804.0570 | |
| dc.identifier | http://arxiv.org/abs/0804.0570 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/212289 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.subject | Discrete Mathematics | |
| dc.title | A Parameterized Perspective on $P_2$-Packings | |
| dc.type | text |