On convexity in split graphs: complexity of Steiner tree and domination

DOI10.1007/s10878-024-01105-1arXiv2210.02288MaRDI QIDQ6123388

N. Sadagopan, P. Renjith, Arusamy Mohanapriya

Publication date: 4 March 2024

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

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

zbMATH Keywords

split graphsdominationSteiner treeparameterized complexitytree-convexcircular-convex split graphs

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Solving problems on generalized convex graphs via mim-width
• Domination in convex and chordal bipartite graphs
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• A kernelization algorithm for \(d\)-hitting set
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Domination in some subclasses of bipartite graphs
• Improved Steiner tree algorithms for bounded treewidth
• The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
• Two Hardness Results on Feedback Vertex Sets
• Unique Covering Problems with Geometric Sets
• Steiner trees, partial 2–trees, and minimum IFI networks
• Incompressibility through Colors and IDs
• Steiner trees, connected domination and strongly chordal graphs
• Tractable Feedback Vertex Sets in Restricted Bipartite Graphs
• The steiner problem in graphs
• Dominating induced matching in some subclasses of bipartite graphs

This page was built for publication: On convexity in split graphs: complexity of Steiner tree and domination