Fast algorithms for some dominating induced matching problems

DOI10.1016/j.ipl.2014.04.012zbMath1370.05170OpenAlexW2012724105MaRDI QIDQ2015144

Min Chih Lin, Michel J. Mizrahi, Jayme Luiz Szwarcfiter

Publication date: 23 June 2014

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

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

zbMATH Keywords

algorithmsgraph theorydominating induced matchings

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 (5)

Perfect edge domination: hard and solvable cases ⋮ Kernelization of edge perfect code and its variants ⋮ Efficient and perfect domination on circular-arc graphs ⋮ Modelling and solving the perfect edge domination problem ⋮ On the dominating induced matching problem: spectral results and sharp bounds

Cites Work

• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Efficient edge domination problems in graphs
• Perfect edge domination and efficient edge domination in graphs
• Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.
• An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching
• Dominating Induced Matchings for P 7-free Graphs in Linear Time
• Efficient Edge Domination on Hole-Free Graphs in Polynomial Time
• Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
• O(n) Time Algorithms for Dominating Induced Matching Problems

This page was built for publication: Fast algorithms for some dominating induced matching problems