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

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

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

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