Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
DOI10.1007/S10878-012-9483-XzbMATH Open1280.05106OpenAlexW2060806117MaRDI QIDQ386432FDOQ386432
Authors: B. S. Panda, D. Pradhan 
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
Recommendations
- A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
- Computing a minimum paired-dominating set in strongly orderable graphs
- Labelling algorithms for paired-domination problems in block and interval graphs
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
NP-completenessperfect matchingchordal bipartite graphspaired-dominationperfect elimination bipartite graphs
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Characterizations of strongly chordal graphs
- Paired-domination in graphs
- Domination in convex and chordal bipartite graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Perfect Elimination and Chordal Bipartite Graphs
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- Labelling algorithms for paired-domination problems in block and interval graphs
- Classes of bipartite graphs related to chordal graphs
- Paired-domination of trees
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- Labeling algorithms for domination problems in sun-free chordal graphs
- 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
- Trees with large paired-domination number
- An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Trees with equal domination and paired-domination numbers.
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
Cited In (22)
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
- Paired-domination problem on distance-hereditary graphs
- Large hypertree width for sparse random hypergraphs
- Linear algorithms for red and blue domination in convex bipartite graphs
- Algorithmic aspects of upper paired-domination in graphs
- An optimal algorithm to find minimum k-hop dominating set of interval graphs
- Computing a minimum paired-dominating set in strongly orderable graphs
- Complexity of paired domination in at-free and planar graphs
- Complexity of distance paired-domination problem in graphs
- A min-max property of chordal bipartite graphs with applications
- A linear-time algorithm for weighted paired-domination on block graphs
- A linear-time algorithm for paired-domination on circular-arc graphs
- Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
- A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
- Upper paired domination versus upper domination
- Complexity of paired domination in AT-free and planar graphs
- Labelling algorithms for paired-domination problems in block and interval graphs
- Paired domination versus domination and packing number in graphs
- Approximation hardness of domination problems on generalized convex graphs
- The Outer-Paired Domination of Graphs
- Complexity of the paired domination subdivision problem
- An optimal algorithm to find minimum \(k\)-hop connected dominating set of permutation graphs
This page was built for publication: Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q386432)
