Linear algorithms for red and blue domination in convex bipartite graphs

DOI10.1007/978-3-030-79987-8_3MaRDI QIDQ2115838OpenAlexFDO

Authors Nesrine Abbas

Publication date 22 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-79987-8_3

zbMATH Keywords

convex bipartite graphblue dominating setred dominating set

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites work

• scientific article; zbMATH DE number 3900787 (Why is no real title available?)
• A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
• An exact algorithm for connected red-blue dominating set
• Domination in convex and chordal bipartite graphs
• Domination in some subclasses of bipartite graphs
• Enumerating minimal dominating sets in chordal bipartite graphs
• Graph Classes: A Survey
• Independent domination on tree convex bipartite graphs
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(3)

• On approximability of optimization problems related to red/blue-split graphs
• A linear kernel for planar red-blue dominating set
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs

This page was built for publication: Linear algorithms for red and blue domination in convex bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115838)