Domination in convex and chordal bipartite graphs

DOI10.1016/0020-0190(90)90147-PzbMath0706.68055OpenAlexW2062476001MaRDI QIDQ918703

Haiko Müller, Dieter Kratsch, Peter Damaschke

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90147-p

zbMATH Keywords

NP-completeness polynomial algorithm domination restricted classes of bipartite graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (48)

Total domination and transformation ⋮ COMPLEXITY OF CERTAIN FUNCTIONAL VARIANTS OF TOTAL DOMINATION IN CHORDAL BIPARTITE GRAPHS ⋮ Domination in some subclasses of bipartite graphs ⋮ Circular convex bipartite graphs: feedback vertex sets ⋮ Right angle free subsets in the plane ⋮ On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ Polar graphs and maximal independent sets ⋮ Induced star partition of graphs ⋮ Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy ⋮ On orthogonal ray graphs ⋮ More results on weighted independent domination ⋮ Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ P versus NPC: minimum Steiner trees in convex split graphs ⋮ On cd-coloring of \(\{P_5,K_4\}\)-free chordal graphs ⋮ A decidability result for the dominating set problem ⋮ Independent domination in finitely defined classes of graphs ⋮ On convexity in split graphs: complexity of Steiner tree and domination ⋮ Star covers and star partitions of double-split graphs ⋮ Tree-Width and Optimization in Bounded Degree Graphs ⋮ Mobile versus point guards ⋮ Global total \(k\)-domination: approximation and hardness results ⋮ The bottleneck independent domination on the classes of bipartite graphs and block graphs. ⋮ Algorithmic aspects of semitotal domination in graphs ⋮ On total \(f\)-domination: polyhedral and algorithmic results ⋮ Edge domination on bipartite permutation graphs and cotriangulated graphs ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ Paths in interval graphs and circular arc graphs ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ The complexity of dissociation set problems in graphs ⋮ Integer linear programming models for the weighted total domination problem ⋮ Differentiating-total domination: approximation and hardness results ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Independent domination versus weighted independent domination ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ On the complexity of the k-chain subgraph cover problem ⋮ The Hamiltonian circuit problem for circle graphs is NP-complete ⋮ Graph Classes with Structured Neighborhoods and Algorithmic Applications ⋮ Chordal bipartite graphs of bounded tree- and clique-width ⋮ Strong Chordality of Graphs with Possible Loops ⋮ Circular Convex Bipartite Graphs: Feedback Vertex Set ⋮ Tractable connected domination for restricted bipartite graphs ⋮ Linear algorithms for red and blue domination in convex bipartite graphs

Cites Work

This page was built for publication: Domination in convex and chordal bipartite graphs