Approximating spanning trees with few branches

DOI10.1007/s00224-014-9556-6zbMath1328.68297OpenAlexW2072083701MaRDI QIDQ2344216

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

theory of computationdesign and analysis of algorithmsapproximation algorithms analysisrouting and network design problems

Mathematics Subject Classification ID

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

Related Items

Decomposition methods based on articulation vertices for degree-dependent spanning tree problems ⋮ Spanning trees with few branch vertices in graphs of bounded neighborhood diversity ⋮ Spanning Trees with Few Branch Vertices

Cites Work

• Lower and upper bounds for the spanning tree with minimum branch vertices
• Bounded-degree spanning tree problems: models and new algorithms
• Approximating the maximum internal spanning tree problem
• Approximation algorithms for connected dominating sets
• Spanning spiders and light-splitting switches
• Relations, models and a memetic approach for three degree-dependent spanning tree problems
• Cutting-plane-based algorithms for two branch vertices related spanning tree problems
• On finding spanning trees with few leaves
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• The Traveling Salesman Problem with Distances One and Two
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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