Algorithms for maximum internal spanning tree problem for some graph classes

DOI10.1007/S10878-022-00897-4MaRDI QIDQ2091107zbMATH OpenOpenAlexWikidataFDO

Authors Gopika Sharma, Arti Pandey, Michael C. Wigal

Publication date 31 October 2022

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.02248

zbMATH Keywords

graph algorithmsNP-completenesschordal graphsbipartite graphsmaximum internal spanning treeoptimal path cover

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: For a given graph $G$, a maximum internal spanning tree of $G$ is a spanning tree of $G$ with maximum number of internal vertices. The Maximum Internal Spanning Tree (MIST) problem is to find a maximum internal spanning tree of the given graph. The MIST problem is a generalization of the Hamiltonian path problem. Since the Hamiltonian path problem is NP-hard, even for bipartite and chordal graphs, two important subclasses of graphs, the MIST problem also remains NP-hard for these graph classes. In this paper, we propose linear-time algorithms to compute a maximum internal spanning tree of cographs, block graphs, cactus graphs, chain graphs and bipartite permutation graphs. The optimal path cover problem, which asks to find a path cover of the given graph with maximum number of edges, is also a well studied problem. In this paper, we also study the relationship between the number of internal vertices in maximum internal spanning tree and number of edges in optimal path cover for the special graph classes mentioned above.

Recommendations

• A survey on algorithms for the maximum internal spanning tree and related problems
• A polynomial time algorithm for finding a spanning tree with maximum number of internal vertices on interval graphs
• Solving the maximum internal spanning tree problem on interval graphs in polynomial time
• A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem
• Approximation Algorithms for the Maximum Internal Spanning Tree Problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A \(2k\)-vertex kernel for maximum internal spanning tree
• A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem
• A linear vertex kernel for maximum internal spanning tree
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• Algorithms and Data Structures
• An optimal path cover algorithm for cographs
• Approximating the maximum internal spanning tree problem
• Approximating the maximum internal spanning tree problem via a maximum path-cycle cover
• Better approximation algorithms for the maximum internal spanning tree problem
• Bipartite permutation graphs
• Bipartite permutation graphs with application to the minimum buffer size problem
• Computing the cutwidth of bipartite permutation graphs in linear time
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• HAMILTONian circuits in chordal bipartite graphs
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• On a class of posets and the corresponding comparability graphs
• On a property of the class of n-colorable graphs
• On finding spanning trees with few leaves
• Optimal path cover problem on block graphs
• Optimal path cover problem on block graphs and bipartite permutation graphs
• Solving the maximum internal spanning tree problem on interval graphs in polynomial time
• The edge Hamiltonian path problem is NP-complete for bipartite graphs

Cited in

(1)

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

This page was built for publication: Algorithms for maximum internal spanning tree problem for some graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2091107)