Approximation algorithms for the maximum weight internal spanning tree problem

DOI10.1007/s00453-018-00533-wzbMath1431.68151arXiv1608.03299OpenAlexW2523081200WikidataQ128784974 ScholiaQ128784974MaRDI QIDQ5919671

Lusheng Wang, Guo-Hui Lin, Dan Wang, Zhi-Zhong Chen, Yong Chen

Publication date: 17 October 2019

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1608.03299

zbMATH Keywords

approximation algorithmperformance analysismaximum weight matchingmaximum weight internal spanning tree

Mathematics Subject Classification ID

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

Related Items (5)

Scatter search for the minimum leaf spanning tree problem ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs ⋮ An approximation algorithm for maximum internal spanning tree ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• Approximating the maximum internal spanning tree problem
• An approximation algorithm for maximum internal spanning tree
• A linear vertex kernel for maximum internal spanning tree
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• On finding spanning trees with few leaves
• Sharp separation and applications to exact and parameterized algorithms
• 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
• A 2k-vertex Kernel for Maximum Internal Spanning Tree
• A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs
• Algorithms and Data Structures

This page was built for publication: Approximation algorithms for the maximum weight internal spanning tree problem