A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs
From MaRDI portal
Publication:4632175
DOI10.1007/978-3-319-39817-4_10zbMath1475.68249OpenAlexW2497553818MaRDI QIDQ4632175
Haodi Feng, Haitao Jiang, Binhai Zhu, Xingfu Li
Publication date: 26 April 2019
Published in: Frontiers in Algorithmics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-39817-4_10
Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Scatter search for the minimum leaf spanning tree problem, An approximation algorithm for maximum internal spanning tree, Approximation algorithms for the maximum weight internal spanning tree problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear algorithm for optimal path cover problem on interval graphs
- Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
- Approximating the maximum internal spanning tree problem
- Spanning trees with at most 3 leaves in \(K_{1,4}\)-free graphs
- A unified approach to domination problems on interval graphs
- Another look at the degree constrained subgraph problem
- Algorithmic graph theory and perfect graphs
- 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
- Neighborhood unions and extremal spanning trees
- Sharp separation and applications to exact and parameterized algorithms
- Algorithms for k-Internal Out-Branching
- 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
- Algorithms and Data Structures
