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

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

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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

(7)

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

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)