The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
From MaRDI portal
Publication:1099628
DOI10.1016/0304-3975(87)90067-3zbMath0638.68062OpenAlexW2058460385MaRDI QIDQ1099628
Andreas Brandstädt, Haiko Müller
Publication date: 1987
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(87)90067-3
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Related Items (66)
On the terminal connection problem ⋮ Domination in some subclasses of bipartite graphs ⋮ Computing a minimum paired-dominating set in strongly orderable graphs ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ The general facility location problem with connectivity on trees ⋮ Induced star partition of graphs ⋮ Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy ⋮ Boundary classes for graph problems involving non-local properties ⋮ Steiner trees for hereditary graph classes: a treewidth perspective ⋮ Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs ⋮ On strictly chordality-\(k\) graphs ⋮ The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ On the computational difficulty of the terminal connection problem ⋮ Unique response Roman domination: complexity and algorithms ⋮ P versus NPC: minimum Steiner trees in convex split graphs ⋮ A decidability result for the dominating set problem ⋮ Algorithmic Aspects of Disjunctive Total Domination in Graphs ⋮ On convexity in split graphs: complexity of Steiner tree and domination ⋮ Star covers and star partitions of double-split graphs ⋮ Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs ⋮ Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs ⋮ Sequentially swapping tokens: further on graph classes ⋮ Cosecure domination: hardness results and algorithms ⋮ Some new algorithmic results on co-secure domination in graphs ⋮ Algorithm and hardness results on neighborhood total domination in graphs ⋮ On computing a minimum secure dominating set in block graphs ⋮ Unnamed Item ⋮ Domination in convex and chordal bipartite graphs ⋮ Mobile versus point guards ⋮ The algorithmic complexity of bondage and reinforcement problems in bipartite graphs ⋮ Algorithmic aspects of semitotal domination in graphs ⋮ Variations of \(Y\)-dominating functions on graphs ⋮ Problems with generalized Steiner problems ⋮ On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Some remarks on the geodetic number of a graph ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ The complexity of dissociation set problems in graphs ⋮ Secure total domination in graphs: bounds and complexity ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ Complexity of Steiner Tree in Split Graphs - Dichotomy Results ⋮ Differentiating-total domination: approximation and hardness results ⋮ Layered graphs: applications and algorithms ⋮ Algorithmic results on double Roman domination in graphs ⋮ Algorithmic aspects of secure connected domination in graphs ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Roman \(\{k\}\)-domination in trees and complexity results for some classes of graphs ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Algorithms and Complexity of Power Domination in Graphs ⋮ Paired Domination in Graphs ⋮ Connected Domination ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ A multivariate analysis of the strict terminal connection problem ⋮ Linear separation of connected dominating sets in graphs ⋮ Weighted connected domination and Steiner trees in distance-hereditary graphs ⋮ Chordal bipartite graphs of bounded tree- and clique-width ⋮ On the Convexity of Paths of Length Two in Undirected Graphs ⋮ Domination problems on P5-free graphs ⋮ A note on the complexity of locating-total domination in graphs ⋮ Revising Johnson's table for the 21st century ⋮ Algorithmic aspects of k-part degree restricted domination in graphs ⋮ A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs ⋮ On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ Tractable connected domination for restricted bipartite graphs
Cites Work
This page was built for publication: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
