P versus NPC: minimum Steiner trees in convex split graphs

DOI10.1007/978-3-030-95018-7_10OpenAlexW4206974987MaRDI QIDQ6102270

N. Sadagopan, P. Renjith, Arusamy Mohanapriya

Publication date: 8 May 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-030-95018-7_10

zbMATH Keywords

dominationSteiner treecircular-convexpath-convextree-convextriad-convex

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Domination in convex and chordal bipartite graphs
• 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
• Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy
• The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
• 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
• The steiner problem in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: P versus NPC: minimum Steiner trees in convex split graphs