A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph

DOI10.1016/j.dam.2012.04.014zbMath1287.05106OpenAlexW2078021604MaRDI QIDQ2446306

Yanyan Li

Publication date: 16 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.04.014

zbMATH Keywords

perfect matchingpaired-dominationconvex bipartite graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Computing a minimum paired-dominating set in strongly orderable graphs ⋮ A linear-time algorithm for weighted paired-domination on block graphs ⋮ Injective coloring of some subclasses of bipartite graphs and chordal graphs ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ Paired Domination in Graphs ⋮ Linear algorithms for red and blue domination in convex bipartite graphs

Cites Work

• 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
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Paired-domination of trees
• Paired domination on interval and circular-arc graphs
• Paired-domination in graphs

This page was built for publication: A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph