Finding a dominating set on bipartite graphs

DOI10.1016/J.IPL.2008.02.009MaRDI QIDQ963425zbMATH OpenOpenAlexFDO

Authors Mathieu Liedloff

Publication date 19 April 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2008.02.009

zbMATH Keywords

algorithmsbipartite graphsdominating setexponential-time algorithmsgraph algorithms

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 4202309
• Dominating Bipartite Subgraphs in Graphs
• Locating domination in bipartite graphs and their complements
• Bipartite Domination in Graphs
• Domination in bipartite graphs
• Dominating sets for split and bipartite graphs
• Domination in Bipartite Graphs and in Their Complements
• A note on domination in bipartite graphs
• Domination in some subclasses of bipartite graphs
• Domination in some subclasses of bipartite graphs

Cites work

• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A note on the complexity of minimum dominating set
• Algorithms for maximum independent sets
• Automata, Languages and Programming
• Design by measure and conquer. A faster exact algorithm for dominating set
• Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes
• Finding a Maximum Independent Set
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 5605070 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• Measure and conquer
• Parameterized and Exact Computation
• Pathwidth of cubic graphs and exact algorithms

Cited in

(15)

• The bottleneck independent domination on the classes of bipartite graphs and block graphs.
• Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA
• Dominator sequences in bipartite graphs
• Exact algorithms for weak Roman domination
• On the complexity of dominating set problems related to the minimum all-ones problem
• A note on domination in bipartite graphs
• STRONG DOUBLY GEODETIC PROBLEM ON GRAPHS
• Strong geodetic problem on complete multipartite graphs
• Dominating Bipartite Subgraphs in Graphs
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Safe sets and in-dominating sets in digraphs
• Algorithms for minimum membership dominating set problem
• Total 2-domination number in digraphs and its dual parameter
• Dominating sets for split and bipartite graphs

This page was built for publication: Finding a dominating set on bipartite graphs

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