On convexity in split graphs: complexity of Steiner tree and domination
From MaRDI portal
Publication:6123388
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
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
