Algorithms for maximum internal spanning tree problem for some graph classes

DOI10.1007/S10878-022-00897-4zbMATH Open1505.90111arXiv2112.02248OpenAlexW4294659499WikidataQ114225848 ScholiaQ114225848MaRDI QIDQ2091107FDOQ2091107

Authors: Gopika Sharma, Arti Pandey, Michael C. Wigal 

Publication date: 31 October 2022

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

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.

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

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

zbMATH Keywords

graph algorithmsNP-completenesschordal graphsbipartite graphsmaximum internal spanning treeoptimal path cover

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Optimal path cover problem on block graphs and bipartite permutation graphs
• An optimal path cover algorithm for cographs
• Bipartite permutation graphs
• HAMILTONian circuits in chordal bipartite graphs
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• On finding spanning trees with few leaves
• Bipartite permutation graphs with application to the minimum buffer size problem
• On a class of posets and the corresponding comparability graphs
• A linear vertex kernel for maximum internal spanning tree
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• The edge Hamiltonian path problem is NP-complete for bipartite graphs
• On a property of the class of n-colorable graphs
• A \(2k\)-vertex kernel for maximum internal spanning tree
• Algorithms and Data Structures
• Approximating the maximum internal spanning tree problem
• Better approximation algorithms for the maximum internal spanning tree problem
• Approximating the maximum internal spanning tree problem via a maximum path-cycle cover
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
• Optimal path cover problem on block graphs
• Computing the cutwidth of bipartite permutation graphs in linear time
• 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

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)