Approximating the maximum internal spanning tree problem

DOI10.1016/j.tcs.2009.08.029zbMath1194.68177OpenAlexW1975444413MaRDI QIDQ1034535

Gábor Salamon

Publication date: 6 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.08.029

zbMATH Keywords

approximation algorithmHamiltonian pathspanning tree leaves

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (20)

A 2k-vertex Kernel for Maximum Internal Spanning Tree ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ Solving the maximum internal spanning tree problem on interval graphs in polynomial time ⋮ Scatter search for the minimum leaf spanning tree problem ⋮ Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem ⋮ A multivariate framework for weighted FPT algorithms ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs ⋮ An approximation algorithm for maximum internal spanning tree ⋮ Unnamed Item ⋮ Complexity of independency and cliquy trees ⋮ Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs ⋮ Approximation algorithms for the maximum weight internal spanning tree problem ⋮ Algorithms for maximum internal spanning tree problem for some graph classes ⋮ Approximating spanning trees with few branches ⋮ Better approximation algorithms for the maximum internal spanning tree problem

Cites Work

• On a class of posets and the corresponding comparability graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On finding spanning trees with few leaves
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Spanning Trees and Optimization Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximating the maximum internal spanning tree problem