Solving the maximum internal spanning tree problem on interval graphs in polynomial time

DOI10.1016/j.tcs.2017.09.017zbMath1393.68075OpenAlexW2757350721MaRDI QIDQ2636496

Binhai Zhu, Haodi Feng, Haotao Jiang, Xingfu Li

Publication date: 5 June 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.09.017

zbMATH Keywords

algorithmpolynomialinterval graphmaximum internal spanning tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (4)

A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ Algorithms for enumerating multiple leaf-distance granular regular \(\alpha\)-subtree of unicyclic and edge-disjoint bicyclic 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
• 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
• 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

This page was built for publication: Solving the maximum internal spanning tree problem on interval graphs in polynomial time