Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree

DOI10.1016/j.ic.2016.11.003zbMath1357.68296OpenAlexW2556960737MaRDI QIDQ729821

Wenjun Li, Yixin Cao, Jianxin Wang, Jian'er Chen

Publication date: 22 December 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2016.11.003

zbMATH Keywords

local searchparameterized computationmaximum internal spanning tree

Mathematics Subject Classification ID

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

Related Items (14)

Dealing with several parameterized problems by random methods ⋮ Parameterized algorithms for edge biclique and related problems ⋮ Scatter search for the minimum leaf spanning tree problem ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem ⋮ Algorithms for enumerating multiple leaf-distance granular regular \(\alpha\)-subtree of unicyclic and edge-disjoint bicyclic graphs ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ Unnamed Item ⋮ Complexity of independency and cliquy trees ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs ⋮ Algorithms for maximum internal spanning tree problem for some graph classes ⋮ On enumerating algorithms of novel multiple leaf-distance granular regular \(\alpha\)-subtrees of trees

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithms -- ESA 2014. 22nd annual European symposium, Wrocław, Poland, September 8--10, 2014. Proceedings
• Spanning trees: A survey
• On the minimum diameter spanning tree problem
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• Approximating the maximum internal spanning tree problem
• Minimum leaf out-branching and related problems
• A linear vertex kernel for maximum internal spanning tree
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Better approximation algorithms for the maximum internal spanning tree problem
• 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
• Representative Families: A Unified Tradeoff-Based Approach
• Approximating the Maximum Internal Spanning Tree Problem via a Maximum Path-Cycle Cover
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• A 2k-vertex Kernel for Maximum Internal Spanning Tree
• Limits and Applications of Group Algebras for Parameterized Problems
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• A randomized linear-time algorithm to find minimum spanning trees
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• Algorithms and Data Structures

This page was built for publication: Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree