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

DOI10.7155/JGAA.00590zbMath1498.05259OpenAlexW3036053968MaRDI QIDQ5049994

Ahmad Biniaz

Publication date: 14 November 2022

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00590

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

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 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
• 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