Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
From MaRDI portal
Publication:2232252
DOI10.1007/978-3-030-68211-8_21OpenAlexW3134137449MaRDI QIDQ2232252
Publication date: 4 October 2021
Full work available at URL: https://arxiv.org/abs/2006.12561
approximation algorithmclaw-free graphcubic graphdepth-first searchinternal spanning treevertex-weighted tree
Related Items (2)
Scatter search for the minimum leaf spanning tree problem ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
Cites Work
- Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
- Approximating the maximum internal spanning tree problem
- The edge Hamiltonian path problem is NP-complete
- An approximation algorithm for maximum internal spanning tree
- A linear vertex kernel for maximum internal spanning tree
- Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
- Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
- Better approximation algorithms for the maximum internal spanning tree problem
- On finding spanning trees with few leaves
- Sharp separation and applications to exact and parameterized algorithms
- Approximating the Maximum Internal Spanning Tree Problem via a Maximum Path-Cycle Cover
- A 2k-vertex Kernel for Maximum Internal Spanning Tree
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The Traveling Salesman Problem for Cubic Graphs
- Algorithms and Data Structures
- Approximation algorithms for the maximum weight internal spanning tree problem
This page was built for publication: Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
