Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
From MaRDI portal
Publication:386432
DOI10.1007/s10878-012-9483-xzbMath1280.05106MaRDI QIDQ386432
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
NP-completeness; perfect matching; chordal bipartite graphs; paired-domination; perfect elimination bipartite graphs
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
An optimal algorithm to find minimum k-hop dominating set of interval graphs, An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs, Upper paired domination versus upper domination, Complexity of paired domination in at-free and planar graphs, Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs, Computing a minimum paired-dominating set in strongly orderable graphs, Linear algorithms for red and blue domination in convex bipartite graphs, Complexity of paired domination in AT-free and planar graphs, A linear-time algorithm for weighted paired-domination on block graphs, Algorithmic aspects of upper paired-domination in graphs, Large hypertree width for sparse random hypergraphs, A linear-time algorithm for paired-domination on circular-arc 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
