Algorithms for maximum internal spanning tree problem for some graph classes

Gopika Sharma (), Arti Pandey () and Michael C. Wigal ()
Additional contact information
Gopika Sharma: Indian Institute of Technology Ropar
Arti Pandey: Indian Institute of Technology Ropar
Michael C. Wigal: Georgia Institute of Technology

Journal of Combinatorial Optimization, 2022, vol. 44, issue 5, No 12, 3419-3445

Abstract: 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.

Keywords: Maximum internal spanning tree; Bipartite graphs; Chordal graphs; Optimal path cover; NP-completeness; Graph Algorithms (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00897-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:5:d:10.1007_s10878-022-00897-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00897-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().