Exact algorithms for minimum weighted dominating induced matching
From MaRDI portal
Publication:521800
DOI10.1007/s00453-015-0095-6zbMath1359.05125OpenAlexW2299776542MaRDI QIDQ521800
Min Chih Lin, Michel J. Mizrahi, Jayme Luiz Szwarcfiter
Publication date: 12 April 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-015-0095-6
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 (3)
A heuristic approximation algorithm of minimum dominating set based on rough set theory ⋮ Modelling and solving the perfect edge domination problem ⋮ Dominating induced matchings of finite graphs and regularity of edge ideals
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exact exponential algorithms.
- On the complexity of the dominating induced matching problem in hereditary classes of graphs
- Efficient edge domination in regular graphs
- On two techniques of combining branching and treewidth
- 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
- Counting models for 2SAT and 3SAT formulae
- Exact algorithms for dominating induced matching based on graph partition
- A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs
- An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching
- A Faster Algorithm for Dominating Set Analyzed by the Potential Method
- Dominating Induced Matchings for P 7-free Graphs in Linear Time
- Even Faster Exact Bandwidth
- A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
- Fourier meets M\"{o}bius: fast subset convolution
- Efficient Edge Domination on Hole-Free Graphs in Polynomial Time
- Inclusion/Exclusion Meets Measure and Conquer
- Dominating Induced Matchings
- A New Algorithm for Generating All the Maximal Independent Sets
- Paths, Stars and the Number Three
- Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
- Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
- Hereditary Efficiently Dominatable Graphs
This page was built for publication: Exact algorithms for minimum weighted dominating induced matching
