Fast algorithms for some dominating induced matching problems
DOI10.1016/J.IPL.2014.04.012zbMATH Open1370.05170OpenAlexW2012724105MaRDI QIDQ2015144FDOQ2015144
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
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
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)
Cites Work
- 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
- An \(O ^{*}(1.1939^{n })\) time algorithm for minimum weighted dominating induced matching
- Efficient edge domination on hole-free graphs in polynomial time
- Efficient dominating and edge dominating sets for graphs and hypergraphs
- On the complexity of the dominating induced matching problem in hereditary classes of graphs
- Dominating induced matchings for \(P _{7}\)-free graphs in linear time
- \(O(n)\) time algorithms for dominating induced matching problems
- Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.
Cited In (12)
- \(O(n)\) time algorithms for dominating induced matching problems
- Perfect edge domination: hard and solvable cases
- Kernelization of edge perfect code and its variants
- Efficient and perfect domination on circular-arc graphs
- Dynamics of nonlinear three-dimensionalwaves on the interface between two fluids in a channel with low-sloping bottom and top
- Modelling and solving the perfect edge domination problem
- On the dominating induced matching problem: spectral results and sharp bounds
- An \(O ^{*}(1.1939^{n })\) time algorithm for minimum weighted dominating induced matching
- Graphs whose vertices of degree at least 2 lie in a triangle
- Exact algorithms for dominating induced matching based on graph partition
- Title not available (Why is that?)
- Exact algorithms for minimum weighted dominating induced matching
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)
