Approximating the maximum internal spanning tree problem

DOI10.1016/J.TCS.2009.08.029zbMATH Open1194.68177OpenAlexW1975444413MaRDI QIDQ1034535FDOQ1034535

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

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

zbMATH Keywords

approximation algorithmHamiltonian pathspanning tree leaves

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (23)

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

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)