Approximation Algorithms for the Maximum Internal Spanning Tree Problem

DOI10.1007/978-3-540-74456-6_10MaRDI QIDQ3525559zbMATH OpenOpenAlexFDO

Authors Gábor Salamon

Publication date 17 September 2008

Published in Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74456-6_10

zbMATH Keywords

approximation algorithmHamiltonian pathspanning tree leaves

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Recommendations

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

Cited in

(15)

• A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem
• Spanning trees: A survey
• Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
• Exact and parameterized algorithms for Max Internal Spanning Tree
• Approximating the maximum internal spanning tree problem
• 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
• A survey on algorithms for the maximum internal spanning tree and related problems
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• Deeper local search for better approximation on maximum internal spanning trees
• Approximating the maximum internal spanning tree problem via a maximum path-cycle cover
• Better approximation algorithms for the maximum internal spanning tree problem
• On finding spanning trees with few leaves
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Algorithms for maximum internal spanning tree problem for some graph classes

This page was built for publication: Approximation Algorithms for 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 Q3525559)