Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
From MaRDI portal
Publication:729821
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
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
