A simple linear time algorithm to solve the MIST problem on interval graphs

DOI10.1016/j.tcs.2022.07.012OpenAlexW4285601507MaRDI QIDQ2166762

Yi Shi, Jianhui Shang, Peng Li

Publication date: 25 August 2022

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

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

zbMATH Keywords

linear time algorithmmaximum internal spanning treeconnected interval graphsnormal orderings

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The longest path problem has a polynomial solution on interval graphs
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
• 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
• Finding Hamiltonian circuits in interval graphs
• Paths in interval graphs and circular arc graphs
• Optimal path cover problem on block graphs and bipartite permutation graphs
• An approximation algorithm for maximum internal spanning tree
• Algorithmic graph theory and perfect graphs
• An optimal path cover algorithm for cographs
• 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
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• Solving the maximum internal spanning tree problem on interval graphs in polynomial time
• LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
• 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
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• A 2k-vertex Kernel for Maximum Internal Spanning Tree
• Algorithms and Data Structures
• Approximation algorithms for the maximum weight internal spanning tree problem

This page was built for publication: A simple linear time algorithm to solve the MIST problem on interval graphs