Linear algorithms for red and blue domination in convex bipartite graphs

DOI10.1007/978-3-030-79987-8_3OpenAlexW3174975592MaRDI QIDQ2115838FDOQ2115838

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

• Graph Classes: A Survey
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• An exact algorithm for connected red-blue dominating set
• Enumerating minimal dominating sets in chordal bipartite graphs
• Domination in convex and chordal bipartite graphs
• Independent Domination on Tree Convex Bipartite Graphs
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• Domination in Some Subclasses of Bipartite Graphs
• Title not available (Why is that?)
• A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph

Cited In (3)

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

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)