Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs

DOI10.1007/978-3-030-68211-8_21OpenAlexW3134137449MaRDI QIDQ2232252

Ahmad Biniaz

Publication date: 4 October 2021

Full work available at URL: https://arxiv.org/abs/2006.12561

zbMATH Keywords

approximation algorithmclaw-free graphcubic graphdepth-first searchinternal spanning treevertex-weighted tree

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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