Exact algorithms for dominating induced matching based on graph partition
From MaRDI portal
Publication:2352792
DOI10.1016/j.dam.2015.04.012zbMath1316.05102arXiv1408.6196OpenAlexW1795017168MaRDI QIDQ2352792
Mingyu Xiao, Hiroshi Nagamochi
Publication date: 6 July 2015
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1408.6196
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 ⋮ Modelling and solving the perfect edge domination problem ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ Complexity and kernels for bipartition into degree-bounded induced graphs
Cites Work
- Dominating induced matchings for \(P_7\)-free graphs in linear time
- A refined exact algorithm for edge dominating set
- Exact exponential algorithms.
- On the complexity of the dominating induced matching problem in hereditary classes of graphs
- Efficient edge domination in regular graphs
- Solving the weighted efficient edge domination problem on bipartite permutation graphs
- Efficient edge domination problems in graphs
- Weighted efficient domination problem on some perfect graphs
- Perfect edge domination and efficient edge domination in graphs
- Exact algorithms for edge domination
- An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching
- Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs
- Efficient Edge Domination on Hole-Free Graphs in Polynomial Time
- Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
This page was built for publication: Exact algorithms for dominating induced matching based on graph partition
