The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs

Recommendations

scientific article; zbMATH DE number 3963856
Tree Convex Bipartite Graphs: $\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth
NP-completeness results for some problems on subclasses of bipartite and chordal graphs
Restrained domination in some subclasses of chordal graphs
Dominating sets for split and bipartite graphs

Cites work

scientific article; zbMATH DE number 3859178 (Why is no real title available?)
scientific article; zbMATH DE number 3919840 (Why is no real title available?)
scientific article; zbMATH DE number 3639144 (Why is no real title available?)
Bipartite permutation graphs
Domination in permutation graphs
On domination problems for permutation and other graphs
Reducibility among combinatorial problems
Steiner trees, connected domination and strongly chordal graphs
The NP-completeness column: an ongoing guide

Cited in

(78)

Cosecure domination: hardness results and algorithms
Roman $\{3\}$-domination in graphs: complexity and algorithms
Steiner trees for hereditary graph classes: a treewidth perspective
scientific article; zbMATH DE number 3963856 (Why is no real title available?)
Upper Clique Transversals in Graphs
On star partition of split graphs
Star covers and star partitions of cographs and butterfly-free graphs
Optimal local identifying and local locating-dominating codes
Unique response Roman domination: complexity and algorithms
P versus NPC: minimum Steiner trees in convex split graphs
On maximal Roman domination in graphs: complexity and algorithms
Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs
Algorithmic aspects of $k$-part degree restricted domination in graphs
Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs
A closer look at Hamiltonicity and domination through the lens of diameter and convexity
Combinatorics and algorithms for quasi-chain graphs
Approximation hardness of domination problems on generalized convex graphs
On convexity in split graphs: complexity of Steiner tree and domination
Some new algorithmic results on co-secure domination in graphs
Star covers and star partitions of double-split graphs
Combinatorics and algorithms for quasi-chain graphs
Computing a minimum paired-dominating set in strongly orderable graphs
Steiner tree in $k$-star caterpillar convex bipartite graphs: a dichotomy
On strictly chordality-$k$ graphs
Linear separation of connected dominating sets in graphs
Tractable connected domination for restricted bipartite graphs
On the computational difficulty of the terminal connection problem
The complexity of dissociation set problems in graphs
The Steiner tree in $K_{1,r}$-free split graphs -- a dichotomy
Domination in some subclasses of bipartite graphs
NP-completeness results for some problems on subclasses of bipartite and chordal graphs
Induced star partition of graphs
Weighted connected domination and Steiner trees in distance-hereditary graphs
Algorithmic aspects of secure connected domination in graphs
On the terminal connection problem
Some remarks on the geodetic number of a graph
Differentiating-total domination: approximation and hardness results
Doubly chordal graphs, steiner trees, and connected domination
Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
Algorithmic aspects of upper paired-domination in graphs
On the complexity of $\{k\}$-domination and $k$-tuple domination in graphs
A note on the complexity of locating-total domination in graphs
Algorithm and hardness results on neighborhood total domination in graphs
Boundary classes for graph problems involving non-local properties
Graph modification problem for some classes of graphs
scientific article; zbMATH DE number 7742925 (Why is no real title available?)
Domination problems on $P_{5}$-free graphs
Variations of $Y$-dominating functions on graphs
A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
On the convexity of paths of length two in undirected graphs
A multivariate analysis of the strict terminal connection problem
Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
Layered graphs: applications and algorithms
Mobile versus point guards
NP-hard graph problems and boundary classes of graphs
Chordal bipartite graphs of bounded tree- and clique-width
Complexity of Steiner tree in split graphs -- dichotomy results
Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
A decidability result for the dominating set problem
Roman $\{k\}$-domination in trees and complexity results for some classes of graphs
Domination in convex and chordal bipartite graphs
On computing a minimum secure dominating set in block graphs
The $k$-hop connected dominating set problem: approximation and hardness
Algorithmic results on double Roman domination in graphs
Algorithmic aspects of disjunctive total domination in graphs
On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
Sequentially swapping tokens: further on graph classes
Connected domination
The general facility location problem with connectivity on trees
The algorithmic complexity of bondage and reinforcement problems in bipartite graphs
Algorithmic aspects of semitotal domination in graphs
Algorithms and complexity of power domination in graphs
Paired domination in graphs
Secure total domination in graphs: bounds and complexity
Bibliography on domination in graphs and some basic definitions of domination parameters
Revising Johnson's table for the 21st century
Problems with generalized Steiner problems

This page was built for publication: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs

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