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

DOI10.1007/978-3-031-25211-2_17MaRDI QIDQ6132536zbMATH OpenOpenAlexFDO

Authors Arusamy Mohanapriya, P. Renjith, 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

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

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

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