Fast algorithms for some dominating induced matching problems

DOI10.1016/J.IPL.2014.04.012MaRDI QIDQ2015144zbMATH OpenOpenAlexFDO

Authors Min Chih Lin, Michel J. Mizrahi, Jayme L. 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

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• \(O(n)\) time algorithms for dominating induced matching problems
• An \(O ^{*}(1.1939^{n })\) time algorithm for minimum weighted dominating induced matching
• Exact algorithms for minimum weighted dominating induced matching
• Dynamics of nonlinear three-dimensionalwaves on the interface between two fluids in a channel with low-sloping bottom and top
• Dominating induced matchings for \(P_7\)-free graphs in linear time

Cites work

• 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 dominating and edge dominating sets for graphs and hypergraphs
• Efficient edge domination on hole-free graphs in polynomial time
• Efficient edge domination problems in graphs
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Perfect edge domination and efficient edge domination in graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.
• \(O(n)\) time algorithms for dominating induced matching problems

Cited in

(12)

• Perfect edge domination: hard and solvable cases
• Exact algorithms for dominating induced matching based on graph partition
• On the dominating induced matching problem: spectral results and sharp bounds
• \(O(n)\) time algorithms for dominating induced matching problems
• An \(O ^{*}(1.1939^{n })\) time algorithm for minimum weighted dominating induced matching
• scientific article; zbMATH DE number 6687769 (Why is no real title available?)
• Modelling and solving the perfect edge domination problem
• Kernelization of edge perfect code and its variants
• Exact algorithms for minimum weighted dominating induced matching
• Efficient and perfect domination on circular-arc graphs
• Graphs whose vertices of degree at least 2 lie in a triangle
• Dynamics of nonlinear three-dimensionalwaves on the interface between two fluids in a channel with low-sloping bottom and top

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

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