Finding a dominating set on bipartite graphs

DOI10.1016/j.ipl.2008.02.009zbMath1185.05111OpenAlexW1967643201MaRDI QIDQ963425

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 graphsgraph algorithmsdominating setexponential-time algorithms

Mathematics Subject Classification ID

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

Related Items (7)

STRONG DOUBLY GEODETIC PROBLEM ON GRAPHS ⋮ Exact algorithms for weak Roman domination ⋮ Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA ⋮ 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 ⋮ Strong geodetic problem on complete multipartite graphs

Cites Work

• Pathwidth of cubic graphs and exact algorithms
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A note on the complexity of minimum dominating set
• Measure and conquer
• Algorithms for maximum independent sets
• Finding a Maximum Independent Set
• Parameterized and Exact Computation
• Graph-Theoretic Concepts in Computer Science
• Automata, Languages and Programming
• Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes
• Unnamed Item
• Unnamed Item
• Unnamed Item

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