Approximating spanning trees with few branches

DOI10.1007/S00224-014-9556-6MaRDI QIDQ2344216zbMATH OpenOpenAlexFDO

Authors Markus Chimani, Joachim Spoerhase

Publication date 12 May 2015

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-014-9556-6

zbMATH Keywords

approximation algorithms analysisdesign and analysis of algorithmsrouting and network design problemstheory of computation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Approximating spanning trees with few branches
• Bounded-degree spanning tree problems: models and new algorithms
• Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem
• scientific article; zbMATH DE number 2086635
• Spanning Trees with Few Branch Vertices

Cites work

• Approximating the maximum internal spanning tree problem
• Approximation algorithms for connected dominating sets
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• Bounded-degree spanning tree problems: models and new algorithms
• Cutting-plane-based algorithms for two branch vertices related spanning tree problems
• scientific article; zbMATH DE number 1305098 (Why is no real title available?)
• scientific article; zbMATH DE number 1305491 (Why is no real title available?)
• scientific article; zbMATH DE number 2038756 (Why is no real title available?)
• scientific article; zbMATH DE number 2086635 (Why is no real title available?)
• scientific article; zbMATH DE number 742978 (Why is no real title available?)
• scientific article; zbMATH DE number 1445319 (Why is no real title available?)
• Lower and upper bounds for the spanning tree with minimum branch vertices
• On finding spanning trees with few leaves
• Reducing to independent set structure -- the case of k-internal spanning tree
• Relations, models and a memetic approach for three degree-dependent spanning tree problems
• Spanning spiders and light-splitting switches
• The Traveling Salesman Problem with Distances One and Two

Cited in

(9)

• Decomposition methods based on articulation vertices for degree-dependent spanning tree problems
• Approximating spanning trees with few branches
• scientific article; zbMATH DE number 1330076 (Why is no real title available?)
• Spanning Trees with Few Branch Vertices
• scientific article; zbMATH DE number 7132826 (Why is no real title available?)
• Spanning trees with few branch vertices in graphs of bounded neighborhood diversity
• scientific article; zbMATH DE number 7691269 (Why is no real title available?)
• Ore-type conditions for existence of a jellyfish in a graph
• Spanning trees minimizing branching costs

This page was built for publication: Approximating spanning trees with few branches

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