Fast algorithms for some dominating induced matching problems
From MaRDI portal
Publication:2015144
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
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
