Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs

DOI10.1007/978-3-031-25211-2_17OpenAlexW4318022957MaRDI QIDQ6132536

P. Renjith, Arusamy Mohanapriya, N. Sadagopan

Publication date: 17 August 2023

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-25211-2_17

zbMATH Keywords

W-hardnessbisplit graphsdichotomy resultsthe Steiner tree problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• A Dirac-type characterization of \(k\)-chordal graphs
• Clustering and domination in perfect graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• HAMILTONian circuits in chordal bipartite graphs
• On strictly chordality-\(k\) graphs
• The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
• Vulnerability of super connected split graphs and bisplit graphs
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• A note on the recognition of bisplit graphs
• Bisplit graphs
• Hamiltonicity in Split Graphs - A Dichotomy
• Steiner trees, connected domination and strongly chordal graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Complexity of Roman {2}-domination and the double Roman domination in graphs
• Bisplit graphs satisfy the Chen-Chv\'atal conjecture

This page was built for publication: Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs