Approximating the maximum internal spanning tree problem

DOI10.1016/J.TCS.2009.08.029MaRDI QIDQ1034535zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• Better approximation algorithms for the maximum internal spanning tree problem
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem

Cites work

• scientific article; zbMATH DE number 1305098 (Why is no real title available?)
• scientific article; zbMATH DE number 2086635 (Why is no real title available?)
• scientific article; zbMATH DE number 742977 (Why is no real title available?)
• scientific article; zbMATH DE number 742978 (Why is no real title available?)
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On a class of posets and the corresponding comparability graphs
• On finding spanning trees with few leaves
• Spanning Trees and Optimization Problems

Cited in

(21)

• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• A survey on algorithms for the maximum internal spanning tree and related problems
• Better approximation algorithms for the maximum internal spanning tree problem
• Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
• A multivariate approach for weighted FPT algorithms
• The maximum \(f\)-depth spanning tree problem
• Complexity of independency and cliquy trees
• A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs
• Solving the maximum internal spanning tree problem on interval graphs in polynomial time
• A \(2k\)-vertex kernel for maximum internal spanning tree
• A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem
• Approximating spanning trees with few branches
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• A multivariate framework for weighted FPT algorithms
• 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 Internal Spanning Tree Problem
• Approximating the maximum internal spanning tree problem via a maximum path-cycle cover
• Scatter search for the minimum leaf spanning tree problem
• A simple linear time algorithm to solve the MIST problem on interval graphs
• Algorithms for maximum internal spanning tree problem for some graph classes

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1034535)