Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs

DOI10.1007/s10878-012-9483-xzbMath1280.05106OpenAlexW2060806117MaRDI QIDQ386432

Mohammad Hasan, H. S. Yoon

Publication date: 9 December 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9483-x

zbMATH Keywords

NP-completenessperfect matchingchordal bipartite graphspaired-dominationperfect elimination bipartite graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (12)

Computing a minimum paired-dominating set in strongly orderable graphs ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ Complexity of paired domination in AT-free and planar graphs ⋮ A linear-time algorithm for weighted paired-domination on block graphs ⋮ Complexity of paired domination in at-free and planar graphs ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ Large hypertree width for sparse random hypergraphs ⋮ Upper paired domination versus upper domination ⋮ A linear-time algorithm for paired-domination on circular-arc graphs ⋮ Linear algorithms for red and blue domination in convex bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Domination in convex and chordal bipartite graphs
• Labelling algorithms for paired-domination problems in block and interval graphs
• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• Characterizations of strongly chordal graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Labeling algorithms for domination problems in sun-free chordal graphs
• Classes of bipartite graphs related to chordal graphs
• Paired-domination of trees
• Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
• Paired domination on interval and circular-arc graphs
• Paired-domination in generalized claw-free graphs
• Characterizations of trees with equal paired and double domination numbers
• An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Paired-domination in graphs

This page was built for publication: Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs